[AtCoder] ABC128 C

bit全検索を使って解く

問題文

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

入力

• 電球iに繋がっているスイッチの二次元配列を list + listの内包表記で作成
  一行毎にlistを作成するとき、その最初の要素は不要なので、2つ目の要素以降を採るために [1:]で範囲を指定

S = [list(map(int, input().split()))[1:] for i in range(M)]

ロジック

• スイッチON/OFFの全ての組み合わせについてbit全検索する

  for sw in range(2**N):

• 各電球のON/OFFをチェックする

• 電球に繋がっているスイッチのうちONになっている個数を cnt とする

  ch = [False] * M
  for i in range(M):
      cnt = 0
      for j in S[i]:
          if sw >> (j-1) & 1:
              cnt += 1

• cnt が2で割り切れるなら、その電球はONになるので ch[i] をTrueにする

      if cnt % 2 == P[i]:
          ch[i] = True
      else:
          ch[i] = False

• 全ての電球がON = 全てTrue になっているスイッチのパターンの数をカウントする

  if all(ch):
      ans += 1

提出したコード

N, M = map(int, input().split())

S = [list(map(int, input().split()))[1:] for i in range(M)]
P = list(map(int, input().split()))

ans = 0

for sw in range(2**N):
    ch = [False] * M
    for i in range(M):
        cnt = 0
        for j in S[i]:
            if sw >> (j-1) & 1:
                cnt += 1
        if cnt % 2 == P[i]:
            ch[i] = True
        else:
            ch[i] = False

    if all(ch):
        ans += 1

print(ans)

https://atcoder.jp/contests/abc128/submissions/24908754