Pythonで毎日AtCoder #47

はじめに

前回

#47

問題

考えたこと
制約を見ると$N,M$が10以下と小さいので力ずくで解けると思い、実装しました。スイッチがon/offの二択なのでbit全探索します。計算量は$O(2^N)$になりますが、$N$が小さいのでTLEしません。要素がそれぞれのスイッチのon/offの状態を表したboolのlistを作り、それぞれの状態での電球の点灯状況を確認します。

n, m = map(int,input().split())
ks = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))

ans = 0
for i in range(2 ** n):
    on = [False] * n
    for j in range(n): #bit全探索
        if ((i>>j) & 1):
            on[n - j - 1] = True
    g = 0
    for j in range(m): #それぞれの電球の状況
        c = 0
        for s in range(1,len(ks[j])):
            if on[ks[j][s]-1]:
                c += 1
        if c % 2 == p[j]: #電球が点灯しているならg+=1する
            g += 1
    if g == m: #すべてのgが点灯しているならans+=1
        ans += 1
print(ans)

まとめ

最近は、計算量が少ないからと甘えて雑な実装しているのでしっかり解説読んできれいに実装できるように精進します。ではまた、おやすみなさい。