【Atcoder】ABC 128 C問題

コンテスト名

AtCoder Beginner Contest 128

考えたこと

。。。なーんもわからない

調べてみよう

bit全探索を使うらしい。*1

スイッチがon,offの2通りだから$2^N$の計算が必要
でもどうやったらbit全探索だと判断できるんだ？

競技プログラミング（AtCoder）において、問題の制約が$N\leq10$とかの極端に小さい場合はbit全探索で解けないかを疑ったほうがいい。
その根拠は、$2^N$は$N=30$くらいで結構大きな数になる点である。

n,m=map(int,input().split())
S=[]

for i in range(m):
    s=list(map(int,input().split()))
    s.pop(0)
    S.append(s)
    
p=list(map(int,input().split()))
count=0
for a in range(2**n):
    bool=True
    for b in range(m):
        sum=0
        for c in S[b]:
            if a>>c-1 & 1:
                sum+=1
        if sum%2!=p[b]:
            bool=False
    if bool==True:
        count+=1
print(count)

(@tttol 様のサイト*2を参考にさせていただきました。)

bit全探索ってなんだ？

スイッチ1がon、スイッチ2がoff、スイッチ3がonだったら[1,0,1]すなわち101のように
2進数として表せる。

全てのスイッチの状態は$2^N$通りあるのでそれらを全探索する。

その際、例えば101においてスイッチ3がONであるかOFFかを調べるときビット操作 *3を使う。

 a>>c-1
 # -1する理由は0indexだから

参考

*1

*2

*3

おまけ

bit全探索について鉄則にも少し書いてあった