7回目のCodeforces。ABC提出ABC正解11Hackで3200点、部屋1位、総合8位。提出は平凡なスピードだったので、Hackのおかげで順位をかなり上げることができた。レーティングも 1610 → 1753 (+143) と初めてDiv1に上がることができ、本当にうれしい。Div1に居続けられるように頑張らねば。そのためにもDぐらいまでは解けるようにならないと。

A 500: Digital Counter

2ケタの数字が与えられる。各桁は7本線のディジタルカウンターとなっている。ただし、各桁のディジタルカウンターの線は何本か壊れている場合があり、表示されている数字が真に表示されるべき数字と異なる場合がある。それでは、与えられた数字を表示する可能性のある真の表示はいくらあるか答えなさい、という問題。

単純に各数字に対して、ありえる正しい数字の個数を調べておいて、与えられた数字の各桁に対応する数を掛け合わせれば答えとなる。

possible = [2,7,2,3,3,4,2,5,1,2]
digit = raw_input()
ans = 1
for i in digit:
    ans *= possible[int(i)]
print ans

B 1000: Modular Equations

正の整数 a, b が与えられる。a mod x = b を満たすｘは何個あるのかを答える問題。a, b ともに最大10⁹なので、1から順番に調べていくとTLEしてしまう。

a mod x = b のとき、a/x = y （整数）とすると、a = x*y + b と書ける。(a-b)/x = y だから、 a-b を割り切れる x を探せばいい。ただし、x <= b だと、 a mod x < b なので b より大きな範囲で探さないといけない。

本番中に思い付いたのは下のコードだが、これはあまり賢くない解法。計算量を減らすために a-b の素因数をすべて求め、それらを掛け合わせて作ることのできる数をすべて計算して出す。これらの数は a-b の約数なので、a-b を割り切ることができる。つまり、その中で b より大きな数の個数を数えれば答えとなる。ただ a = b のときは、a より大きなすべての x で a mod x = b となるので、"infinity"と答える。

賢い解法はsqrt(a-b)までの範囲について割り切れるかどうかを探索する場合だと思うが、まだその解法をきちんと理解していないので、それはまた後日。

def factor(n):
    i = 2
    res = []
    while i*i <= n:
        tmp = 0
        while n%i == 0:
            tmp += 1
            n /= i
        if tmp > 0: res.append([i,tmp])
        i += 1
    if n > 1:
        res.append([n,1])
    return res

a,b = map(int,raw_input().split())
if a == b:
    print "infinity"
else:
    ans = 0
    fact = factor(a-b)
    ls = [1]
    for i,j in fact:
        ls += [ele*(i**k) for k in range(1,j+1) for ele in ls]
    print sum(1 for ele in ls if ele > b)

C 1500: Treasure

"("、")"、"#" からなる文字列が与えられる。各 "#" は1つ以上の ")" に置き換えなければならず、置き換え後に次の条件を満たすようにしたい。

文字列中の "(" と ")" の数は等しい
"(" と対応しない ")" がない

これらの条件を満たすような "#" の置き換えがあるかどうか、あるなら左の "#" から順番に何個の ")" に置き換えるのかを答える問題。置き換え方に複数の方法がある場合はどれか一つを答えればよい。

一見すると難しそうな問題だが、落ち着いて考えると簡単なことに気付く。条件2は、左から "(" と ")" の個数を数えていったとき、常に "(" の個数 ≧ ")"の個数 でないといけない、と言い換えることができる。つまり ")" は文字列右側の方に固まっていた方が都合のいいことがわかる。したがって、途中の "#" はできるだけ少ない ")" で置き換え、最後の "#" を条件１を満たすのに必要な数の ")" で置き換えると、２つの条件を満たす可能性がもっとも高いことがわかる。そういうふうに置き換えた後は条件をきちんと満たしているかどうかを確認してやればいい。置き換えの仕方も単純なので出力も容易である。

s = raw_input()
sharp = s.count("#")
s = s.replace("#",")",sharp-1)   # 最後の"#"以外を１つの")"に置き換え
need = s.count("(")-s.count(")")
s = s.replace("#",")"*max(1,need)) # 最後の"#"も1つ以上の")"に置き換える
balance = 0
for i in s:
    if i == "(":
        balance += 1
    else:
        balance -= 1
        if balance < 0:
            print -1
            break
else:
    for i in range(sharp-1):
        print 1
    print need