ABC 128 C - Switches 緑コーダーですが何か？その３

緑のしいだよ、緑コーダーですが何か？第3回目だよ。３の倍数唯一の素数！いやーめでたい

今回の問題はこちら

ABC 128 C - Switches

https://atcoder.jp/contests/abc128/tasks/abc128_c

きたよ全探索。。。昨日のコンテストでもでて慣れてないとめっちゃじかんかかるよねこれとりまやっていきましょ

解法

制約がめっちゃ小さいので全探査して数える。 Mの値が固定ならその分for書いてもいいんだけどミスりやすいし可変にも対応できる方法は持っておいたほうがいいかな。

全探索の方法

やりかたは色々あるけど主流の２つ（わたしが２つしか知らんだけ）を

bit全探査
itertool

bitはまたまとめると思う。たくさんの人がまとめてるからそっちを見てね。 itertoolも簡潔でわかりやすいからおすすめ

実装１

方針

一度すべて受け取りスイッチに繋がってるか否かで[0 1] のリストを作る
１で作ったリストを使って内積を取り偶奇を判断する。

   N,M = map(int,input().split())
   s = []
   for i in range(M):
       dp = [0]*(N)
       k,*tmp = list(map(int,input().split()))
       for j in tmp:dp[j-1]=1
       s.append(dp)
   p = list(map(int,input().split()))
   ans = 0
   for i in range(1<<N):
       tmp = 0
       dp = [0]*M
       for I in range(M):
           for j in range(N):
               t = i>>j&1
               dp\[I] += s[I\][j] * t
       for e,i in enumerate(dp):
           dp[e] = i%2
       if dp == p:
           ans+=1
   print(ans)

実装２

方針

リストではなく数値で管理する。
内積ではなくビットの論理和を取り１の数の偶奇を判断する。

   N,M = list(map(int, input().split()))
   S = []
   for i in range(M):
       tmp = list(map(int, input().split()))
       t = 0
       for j in tmp[1:]:
           t += 1 << (j - 1)
       S.append(t)
   P = list(map(int, input().split()))
   ans = 0
   for i in range(1 << N):
       f = 0
       for s, p in zip(S, P):
           t = i & s
           c = bin(t).count('1') % 2
           if c == p:f+=1
       if f == M:
           ans += 1
   print(ans)

おまけ(itertool)

    import itertools
    N,M = map(int,input().split())
    s = []
    for i in range(M):
        dp = [0]*(N)
        tmp = list(map(int,input().split()))
        for j in tmp[1:]:dp[j-1]=1
        s.append(dp)
    p = list(map(int,input().split()))
    ans = 0
    for i in itertools.product([0, 1], repeat=N):
        tmp = 0
        dp = [0]*M
        for I in range(M):
            for j in range(N):
                dp\[I] += s[I\][j] * i[j]
        for e,j in enumerate(dp):
            dp[e] = j%2
        if dp == p:
            ans+=1
    print(ans)

あとがき

Bitの内容はやくまとめないと特に縦と横のやつ