読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

Codeforces Round #162 (Div. 2) C・D問題

競技プログラミング codeforces python

昨日の記事で解けていなかった問題を終わってから思いついたので書いとく。

C問題

ある範囲にリスがいて、入力文字列に従ってそれが左半分か右半分に移動する(どんどん範囲は狭くなる)。
このときリスがi番目の入力でいた位置に対して、座標の左から順番に番号iを出力する

解法

よく考えると単純な話で、左に移動すればそれより右、右に移動すればそれより左の位置関係が確定する。
なので左と右の2つのデータを持っておけば良い。

nを入力長とした時外側のループがO(n)なので、pythonのリストでinsert(0, i)とかするとこちらもO(n)だから全体でO(n^2)になって終わらない。
代わりにO(1)のappendを使って最後にreverse()すればよい、この時全体でO(n)
あるいはcollections.dequeを使っても良い。

イテレータを使ってO(1)で効率的に挿入できる言語なら一つのリストでも書けそう

ソースコード

list版
import sys
import collections
import math

stone = sys.stdin.readline().strip()

left = []
right = []
i = 0
for s in stone:
    i += 1
    if s == 'l':
        right.append(i)
    else:
        left.append(i)

for p in left:
    print p
right.reverse()
for p in right:
    print p
deque版
import sys
import collections
import math

stone = sys.stdin.readline().strip()

left = collections.deque()
right = collections.deque()
i = 0
for s in stone:
    i += 1
    if s == 'l':
        right.appendleft(i)
    else:
        left.append(i)

for p in left:
    print p
for p in right:
    print p

D問題

隣り合う数字が互いに素でないものだけを使った最長増加部分列の長さを求める。

解法

与えられた数字を素因数分解して、素因数に対して動的計画法
素朴な素因数分解でも通った。
書いた素因数分解の計算量がよくわからないけどだいたい入力の数値をmとした時O(\sqrt{m})ちょいぐらいなので、入力長をnとすると全体でO(n\sqrt{m})の解(?)
最長の入力の場合にはm = nなのでO(n\sqrt{n})(?)

ソースコード

import sys
import collections
import math

def divisors(n):
    temp = n
    if n <= 2:
        return
    if  temp % 2 == 0:
        while  temp % 2 ==0:
            temp /= 2
        yield 2
    for i in xrange(3, int(math.sqrt(n)) + 1, 2):
        if  temp % i == 0:
            while  temp % i == 0:
               temp /= i
            yield i
    if temp > 1:
        yield temp

n = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())


length = collections.defaultdict(lambda: 0)

for n in A:
    primes = list(divisors(n))

    maximum = 0
    for p in primes:
        length[p] = max(length[p], length[p] + 1)
        maximum = max(maximum, length[p])

    for p in primes:
        length[p] = maximum

    if len(primes) == 0:
        length[n] = 1
#    print length, primes

print max(length.values())
-->