ABC041-D 徒競走

青diff下位に設定されていて比較的昔のコンテストだったので解けるだろうと思ったが苦戦した。 結局わからず解説AC。典型ということだがこのdiffだと初見でも解けた人が多そう。

公式解説pdfがわかりやすい。 しかし、「vからS−{v}へ向かう有向辺がない」を判定する部分で二重ループを書いてしまった。 これでも通るのだが他人のコードを見ていると、有向グラフ部分もbitで表現することで簡潔に書けていたので、今後使っていきたい。 コメントをつけて書き直した。

N, M = map(int, input().split())
b = [0]*N
for _ in range(M):
    x, y = map(int, input().split())
    b[x-1] += 1<<(y-1)
    # x から yへの辺があるときb[x-1]のy-1 bit目が1になるようにする
dp = [0]*(1<<N)
dp[0] = 1
jbs = [(j, 1<<j) for j in range(N)] 
for i in range(1<<N):
    for j,jb in jbs:
        if i&jb<1 and i&b[j]<1:
            # jは1bitだけ1、i&j=0。 jからiに向かう有向辺がない
            dp[i|jb]+=dp[i] 
print(dp[-1])