Atcoder ABC229 振り返り

　バーチャルで参加しました．(207位)尺取り法というアルゴリズムを初めて知りました．また，実装してから初めてUnion Findを使う問題に当たりました．解説でUnion Findを使うとだけ読んでから自力でAC出来たのは良かった点です．自力でUnion Findを使うと考え実装出来るようにしていきたい．

A - First Grid【AC】

　2WAもしてしまった……

s1 = input()
s2 = input()
if (s1 == ".#" and s2 == "#.") or (s1 == "#." and s2 == ".#"):
    print("No")
else:
    print("Yes")

B - Hard Calculation【AC】

pythonは数字と文字の変換が簡単なのでこんな書き方も出来ます．for~else~と書くと，for文の中でbreakされることが無かったときのみ，else文の処理がされます．

A, B = input().split()
for i in range(1, min(len(A), len(B))+1):
    if int(A[-i]) + int(B[-i]) >= 10:
        print("Hard")
        break
else:
    print("Easy")

C - Cheese【AC】

　ナップサック問題かと思いきや，乗せるチーズの量は小数でも良いので，貪欲に価値の高いチーズから使っていけば良い．

N ,W = map(int, input().split())
cheese = []
for _ in range(N):
    a, b = map(int, input().split())
    cheese.append([a, b])

cheese = sorted(cheese)[::-1]
now_cheese = 0
good = 0

for a, b in cheese:
    if W-now_cheese >= b:
        now_cheese += b
        good += b*a
    else:
        good += a*(W-now_cheese)
        break
print(good)

D - Longest X【解説AC】

　rを右側のインデックス，iを左側のインデックスとして，i=0, r=0とします．list[i:r]が条件を満たすまでrを増やしていきます．条件を満たさなくなったら，条件が満たされるようになるまでiを増やしていきます．条件が満たされたらまたrを増やし……と繰り返す事でO(N)で全て探索できます．累積和の始めの0をちゃんと加えて置くことに注意します．

S = input()
K = int(input())
count_list = [0]
cou = 0
for s in S:
    if s == ".":
        cou += 1
    count_list.append(cou)

ans = 0
r = 0
i = 0
while i < len(S):
    if r < len(S) and count_list[r+1] - count_list[i] <= K:
        ans = max(ans, r-i+1)
        r += 1
    else:
        i += 1
print(ans)

E - Graph Destruction【解説AC】

　ぱっと見Union Findか？と思ったけれど使い方が思い付かず解説を見た．逆順に処理をすればよいと言うところを読み後は自力で実装出来た．連結非連結を求める問題ではUnion Findが使えないか疑うこと，処理を逆順から行うと上手く行くことがあると言うことを念頭に置く．以前実装したUnion Findをすんなり使用できたので良かった．

N, M = map(int, input().split())
node = {}
class Unionfind:
    実装略
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    node.setdefault(a, [])
    node[a].append(b)

uf = Unionfind(N)
ans_list = [0]
ans = 0
for i in range(N-1, 0, -1):
    ans += 1
    if i not in node.keys():
        ans_list.append(ans)
        continue
    for j in node[i]:
        if not uf.same(i, j):
            uf.unite(i, j)
            ans -= 1
    ans_list.append(ans)

for i in ans_list[::-1]:
    print(i)