atcoder147cが分からず困ってます。

Question

atcoderで下記問題に対して
問題
参考URL

下のコードで回答されている方がいて、
この11行目からのbit演算の処理が理解できず困っています。
ここではどのような処理が行われているのでしょうか？
ご教示よろしくお願いいたします。

N = int(input())

evidences = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        evidences[i].append((x - 1, y))

result = 0
for i in range(1, 2 ** N):
    consistent = True
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        for x, y in evidences[j]:
            if (i >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print(result)

Answer 1

iの２進数表記は証言をする人の組み合わせを表しているみたいですね。例えばN=3ならiは1,2,3...7になるわけですが、それを二進数で表し、人の名をアイウとすれば、次のように全組み合わせのパターンが網羅できます。

001 アだけ
010 イだけ
011 アとイ
100 ウだけ
101 アとウ
110 イとウ
111 アイウ全員

次に上の組み合わせ全てについて、全員の証言全てがY=1かどうか、つまり矛盾がないかをテストします。
そして一致している時は人数を数え、その最大の数を探すと言うアルゴリズムのようです。

証言者の組み合わせが列挙できれば、必ずしもビット列で表現する必要はなさそうですけれども、計算量でもメモリ効率でもこのアルゴリズムを超えるのは難しそうです。

Comments

[syuheisyosinsya]

0と1の2パターンのN乗を縦軸i横軸jで探索するんですね！
やっと解決できました。ありがとうございます！