Atcoder ABC216 振り返り - hirohirohirohirosのブログ

　Dは解説ACして2通りの解法で解きました．特に二つ目は，DAG，トポロジカルソートと新しい事を学べたので良かったです．

A - Signed Difficulty【AC】

　今までa bなどの標準入力は，脳死でinput().split( )と受け取ってましたが，これはinput()で"a b"という文字列を受け取り，split()で引数の文字で分離すると言うことをやっています．split()で引数に何も入れないと，空白扱いになります．標準入力は大抵空白区切りなので，split()で分離出来ていました．今回小数点の.で区切りたいので，split(".")として分離します．

X, Y = input().split(".")
if 0 <= int(Y) <= 2:
    print(X+"-")
elif 3 <= int(Y) <= 6:
    print(X)
else:
    print(X+"+")

B - Same Name【AC】

　setを使えば同じ要素が複数存在することはありません．

N = int(input())
name = set()
for _ in range(N):
    name.add(input())
if N != len(name):
    print("Yes")
else:
    print("No")

C - Many Balls【AC】

　0からNに向けて2倍したり，1足したりするのは難しそうなので，Nから0に向けて割る2したり-1したりします．割れるなら2で割った方がより少ない回数で0に出来るので，まず割れるか確認します．逆向きに処理してるので，最後の出力で逆順にするのを忘れないようにします．

N = int(input())
ab = []

while N != 0:
    if N % 2 == 0:
        ab.append("B")
        N //= 2
    else:
        ab.append("A")
        N -= 1

print("".join(ab[::-1]))

D - Pair of Balls【解説AC】

　貪欲法を使う解法(公式解説)と貪欲法を使わない解法(ユーザー解説https://kanpurin.hatenablog.com/entry/2021/08/29/230502)を両方実装します．(これで貪欲法が使えるイメージが沸かなかったため)

貪欲法を使う解法

　貪欲に，取り出せるボールがあるならどんどん取り出していって，全てボールを取り出せればYes，そうでないならNoとなります．
　愚直に，全ての筒を見て，同じ色があれば取り除いて……を繰り返すと，全て取り除くのにN回と全ての筒を見るのにM回でO(NM)かかってしまい，間に合いません．
　そこで，cnt[i] = 一番上の色がiである筒の番号　としたリストを作ります．cntの初期値は全て-1としておきます．始め，筒の先頭を全て見て，cntを埋めていきます．そこで，cnt[i]を埋めようとし，-1でなかったら，それは同じ色が二つあるということなので，取り除くことが出来ます．そのことを意味するキューqueに筒の番号のペアをpushします．
　キューからペアをpopし，その筒からボールを取り出します．新しく先頭になったボールの色を確認し，cntを埋めます．cntが-1でなかったら，同じ色のボールが既にあるということなので，キューに筒の番号のペアをpushします．
　これをキューが空になるまで繰り返します．全てのボールが取り出せるなら，繰返し回数がNになるので，繰返し回数を数えておくことで判定が出来ます．

from collections import deque
N, M = map(int, input().split())
pipe = []
cnt = [-1 for _ in range(N)]
que = deque([])
for i in range(M):
    k = input()
    a = deque([int(i)-1 for i in input().split()])
    pipe.append(a)
    if cnt[a[0]] != -1:
        que.append((cnt[a[0]], i))
        cnt[a[0]] = -1
    else:
        cnt[a[0]] = i

n = 0
while que:
    q = que.popleft()
    pipe[q[0]].popleft()
    if len(pipe[q[0]]) > 0:
        if cnt[pipe[q[0]][0]] != -1:
            que.append((cnt[pipe[q[0]][0]], q[0]))
            cnt[pipe[q[0]][0]] = -1
        else:
            cnt[pipe[q[0]][0]] = q[0]

    pipe[q[1]].popleft()
    if len(pipe[q[1]]) > 0:
        # print(pipe[q[1]][0])
        if cnt[pipe[q[1]][0]] != -1:
            que.append((cnt[pipe[q[1]][0]], q[1]))
            cnt[pipe[q[1]][0]] = -1
        else:
            cnt[pipe[q[1]][0]] = q[1]
    
    n += 1

if n == N:
    print("Yes")
else:
    print("No")

DAGを使う解法

　貪欲法を使わず，グラフの問題として解く解法です．
　 $a_{i,j}とa_{i,j+1}$ があるとき， $a_{i,j}→a_{i,j+1}$ となるように有向辺を張ります．このとき，閉路があったら答えはNoです．
　なぜなら， $a_{i,j}→a_{i,j+1}$ の時、 $a_{i, j}$ を取り出さないと $a_{i, j+1}$ を取り出す事が出来ず， $a_{i,j+1}→a_{i,j}$ の時， $a_{i, j+1}$ を取り出さないと $a_{i, j}$ を取り出す事が出来ず，この辺が両方存在する閉路だったら，お互い取り出すためにはお互いを先に取り出す必要があるデットロックの状態になるからです．
　無向辺の閉路はUnion Findで求められますが，有向辺の閉路では求められません．よってトポロジカルソートを利用します．
　トポロジカルソートはノードを一直線に並べて，グラフ全体が→の辺のみになるように並び替えるソートのことです．←の辺が存在しなければ，どのように並べても問題ありません．閉路が存在するならば，どのように並べても必ず←の辺が存在してしまいます．
　有向無閉路グラフをDAGと言います．今回の問題は， $a_{i,j}→a_{i,j+1}$ となるように有向辺を張ったとき，これがDAGになるか？という問題に言い換えられます．
　そして，上述のことから，トポロジカルソートが可能ならDAGです．これは必要十分条件であることがわかります．よって今回の問題は， $a_{i,j}→a_{i,j+1}$ となるように有向辺を張ったとき，トポロジカルソートが可能か？という問題になります．
　後はトポロジカルソートを実装します．ソートの結果，ノードの数が減っていたら，トポロジカルソート出来ず漏れたノード=閉路があったということなので，ソート失敗とします．

from collections import deque
N, M = map(int, input().split())
ok = False
edge = [[] for _ in range(N)]
dag = [0 for _ in range(N)]
for _ in range(M):
    k = int(input())
    a = [int(i)-1 for i in input().split()]

    for i in range(k-1):
        edge[a[i]].append(a[i+1])
        dag[a[i+1]] += 1

ans = [i for i in range(N) if dag[i] == 0]
que = deque(ans)
while que:
    q = que.popleft()
    for e in edge[q]:
        dag[e] -= 1
        if dag[e] == 0:
            que.append(e)
            ans.append(e)
if len(ans) == N:
    print("Yes")
else:
    print("No")