ABC023復習

　昨日AtCoder Beginner Contest 023 に参加しました。結果はボロボロ..orzせめてC問題はちゃんと解きたかったなあ。

abc023.contest.atcoder.jp

珍しくちゃんと全部復習したので上げることにしました。ブログを書くことで復習へのモチベが上がると嬉しいですね。

A：加算王

　まあワンライナーでいきますよね

print sum(map(int, list(raw_input())))

B：手芸王

　解説では素直にシミュレーションしても十分間に合うってことだったんですが、pythonでstringの連結はあんまりやりたくなかったのでこのような形にしました。真ん中から見て行って、不正なブロックをくっつけている場合はその時点で-1を返します。文字列作ってないだけでやってることは一緒ですね。

N = int(raw_input())
S = list(raw_input())
block = ["a", "b", "c"]
if N % 2 == 0:
    print -1
else:
    center = N / 2
    for i in range(center+1):
        if S[center-i] == block[(1-i) % 3] and S[center+i] == block[(1+i) % 3]:
            continue
        print -1
        break
    else:
        print center

C：収集王

　全マスをチェックするのは計算量的に絶対無理って分かってたんですが、良い手が思いつかず部分点だけ取りに行きました。最後の二重カウントを省くのがN回回すだけで済むとなぜ気付かなかったのか..

from collections import defaultdict as ddict
R, C, K = map(int,raw_input().split(" "))
N = int(raw_input())
rc = [0 for i in range(R)]
cc = [0 for i in range(C)]
candy = [None for i in range(N)]
for i in range(N):
    r, c = map(int,raw_input().split(" "))
    candy[i] = (r-1,c-1)
    rc[r-1] += 1
    cc[c-1] += 1
rn = ddict(int)
cn = ddict(int)
for i in range(R):
    rn[rc[i]] += 1
for i in range(C):
    cn[cc[i]] += 1
count = 0
for key in rn:
    count += rn[key] * cn[K-key]
for r, c in candy:
    if rc[r] + cc[c] == K:
        count -= 1
    elif rc[r] + cc[c] == K + 1:
        count += 1
print count

D：撃墜王

　これもオーダーがきつかったですね。最初から部分点狙いでbit-DPしてみたけどそれでも間に合わないっていう(^^;;) chokudaiさんも仰ってましたけど、二分探索をちゃんと使いこなせるようになりたいです。

def check(X, H, S, N):
    time_limit = [0 for i in range(N)]
    for i in range(N):
        tmp = (X - H[i]) / S[i]
        if tmp < 0:
            return False
        if tmp < N:
            time_limit[tmp] += 1
    count = 0
    for i in range(N):
        count += time_limit[i]
        if count > i + 1:
            return False
    else:
        return True

N = int(raw_input())
H = [0 for i in range(N)]
S = [0 for i in range(N)]
for i in range(N):
    H[i], S[i] = map(int,raw_input().split(" "))
left = max(H) - 1
right = max(H[i] + S[i]*(N-1) for i in range(N))
while right - left > 1:
    mid = (left + right) / 2
    if check(mid, H, S, N):
        right = mid
    else:
        left = mid
print right

いつになったらビギナーを脱せるんですかねえ。まあ頑張ります。