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

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

C問題

Problem - C - Codeforces

ある範囲にリスがいて、入力文字列に従ってそれが左半分か右半分に移動する(どんどん範囲は狭くなる)。
このときリスが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問題

Problem - D - Codeforces

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

解法

与えられた数字を素因数分解して、素因数に対して動的計画法。
素朴な素因数分解でも通った。
書いた素因数分解の計算量がよくわからないけどだいたい入力の数値を $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())