Bit全探索の問題ABC(147C)

bit全探索(ABC147C)

参考URL

これはめちゃくちゃわかりやすかった

参考動画

この問題の基本方針はこちらの解説で

問題文

AtCoderのABC147C

この問題は自分がつまずいたので、後で見返してすぐ思い出せるようにメモの意味で投稿。

説明してない部分とくどい部分があって文はカオス。

あとC問題にしてはムズスギ（個人的感想）

僕の解答

N = int(input())
testimony = [[None for _ in range(N)] for _ in range(N)]
person = [None] * N

for i in range(N):
    person[i] = int(input()) #i番目のpersonの証言の数
    for _ in range(person[i]):
        j, good_or_bad = map(int, input().split())
        j -= 1
        testimony[i][j] = good_or_bad
        #i番目の人がj番目の人のことをgood_or_badって思ってるよーってこと。

ans = 0
for i in range(1, 1<<N):
    which_person = [None] * N
    for j in range(N): #j番目の人を見てる。
        which_person[j] = i>>j & 1
    ok = True
    for j in range(N):
        if(which_person[j]): #j番目の人が正直者である時のみ、可否を見れば良い。
            for k in range(N):
                #これ以降でj番目の人が正しいこと言ってるのか否かを調べてる。
                if testimony[j][k] == None: 
                    continue
                if testimony[j][k] != which_person[k]: #which_personってのは、全探索で仮定しているパターン１つに過ぎない
                    ok = False
    if ok:
        ans = max(ans, which_person.count(1))
print(ans)

まずは登場人物の数Nを読み込んでいる。

N = int(input())
testimony = [[None for _ in range(N)] for _ in range(N)]
person = [None] * N

配列を0からスタートするようにしたので、登場人物は人0から始まり人N-1までとし、人0のことを0番目の人と、以下では呼ぶものとする。
そして、C言語風に書けば、int testimony[N][N]のような配列を用意している。testimony[i][j]という要素の意味は、この要素には0か1かNoneが入っているわけだけど、0の場合、i番目の人はj番目の人を不親切だという証言をしていて、1ならj番目の人は正直者だという証言をしている。Noneなら、i番目の人はj番目の人に対して何も言っていない。

最後にpersonというリストを作っているが、これはperson[i]が3とかなら、i番目の人が3つの証言を持っているって意味になる。

そしてi番目の人がしている証言はtestimonyに入れるわけだから、例えばperson[i]が3だとしたら、testimony[i]の要素のうちNoneでないものが3つあることになる。もしiさんがa, b, c番目の人に対してこいつらは全員正直者だ！という証言を持つ場合、testimony[i][a]=testimony[i][b]=testimony[i][c]=1となる。

for i in range(N):
    person[i] = int(input())
    for _ in range(person[i]):
        j, good_or_bad = map(int, input().split())
        j -= 1
        testimony[i][j] = good_or_bad

これは実際にN人の人がしている証言を配列に格納している部分。まずはi番目の人が何個の証言をしているかを読み込み、例えば3個だとしたら、3回ループさせるようにしている。ループ中身は

        j, good_or_bad = map(int, input().split())
        j -= 1
        testimony[i][j] = good_or_bad

これは何をしているかというと、good_or_badってのは正直者かどうか、0か1かを入れる変数。jはというと、もしここで読み込んだjをそのまま配列の要素としてtestimony[i][j] = ...としてしまうと、それはj+1番目の人への証言になってしまう。僕らの感覚でいう1番目ってのは、配列ではtestimony[i][0]なんだから、ここを

j -= 1

で調整している。

以下全探索のメインのところ

ans = 0
for i in range(1, 1<<N):
    which_person = [None] * N
    for j in range(N): #j番目の人を見てる。
        which_person[j] = i>>j & 1
    ok = True
    for j in range(N):
        if(which_person[j]): #j番目の人が正直者である時のみ、可否を見れば良い。
            for k in range(N):
                #これ以降でj番目の人が正しいこと言ってるのか否かを調べてる。
                if testimony[j][k] == None: 
                    continue
                if testimony[j][k] != which_person[k]: #which_personってのは、全探索で仮定しているパターンに過ぎない
                    ok = False
    if ok:
        ans = max(ans, which_person.count(1))
print(ans)

一行目の

for i in range(1, 1<<N):

てところは

for i in range(1, 2**N):

を格好つけて書いただけ。（格好というか、もしかしたらbit全探索をしますよ！というのを知らせるのにもよいのかも。それ以外の意味はあるのかこれ...）あと、1から始めている理由は、もし正直者が一人もいないならans = 0になり、ansはもともと0で初期化してるし、わざわざこの正直者がいないというパターンをループに含めなくてもいいから。別に深い意味はないしあんまり変わらないから0を含めてもいいけど、まぁそこはどうでもいい。

for i in range(1, 1<<N):
    which_person = [None] * N
    for j in range(N): #j番目の人を見てる。
        which_person[j] = i>>j & 1

ここら辺から全探索のフィナーレって感じ。全探索ってそもそも何だったかって考えると、仮定を検証しているわけだ。つまり、i=1, 2, 3, ...., 2** N - 1っていう数に対して、一個一個これは答えになりうる？入力と矛盾ない？と確かめているわけだ。とりあえずiが答えだとしたらと仮定→矛盾がないか確認→矛盾してたら次のiに移行、この繰り返し。

で、次のjのループが大事で、今iという数字はどうですか？っていうループの中のjのループに入るわけだけど、iは例えば、10なら(N=5としましょうか)01010となる。これはどういう過程を置いてるかというと、右から見ていって
- 人0は親切ではない
- 人1は正直
- 人2は親切ではない
- 人3は親切
- 人4は親切ではない
のようにしている。気を付けなくてはならないのは、これは特定の誰かの証言のことではない!
これはbit全探索でこちらがこのパターンはどうかと試しているお前の仮定だ！
(さっきこれをごっちゃにしてよくわからなくなっていたので自分への戒め...)
which_personってのはiを二進数表記した時のbitを、LSBがwhich_person[0]、（途中略）、MSBがwhich_person[N-1]に入るようにしたってだけ。つまりwhich_personにはあなたの仮定の証言が入った！

#iとjのループなう
    ok = True
    for j in range(N):
        if(which_person[j]): #j番目の人が正直者である時のみ、可否を見れば良い。
            for k in range(N):
                #これ以降でj番目の人が正しいこと言ってるのか否かを調べてる。
                if testimony[j][k] == None: 
                    continue
                if testimony[j][k] != which_person[k]: #which_personってのは、全探索で仮定しているパターンに過ぎない
                    ok = False

which_pesonで0が割り振られている人はどうでもよい。僕がそいつは嘘つきだと決めつけて（仮定して）いるので、そいつが誰誰はああでこうでと言っていてもその証言を聞く必要はないからだ。大事なのは、which_personで1を割り振られた人たち、例えば01010(i = 10)で言うなら、人1と人3の証言が大事になってくる。今僕は人1と人3の言っていることは正しいと仮定している。本当に正しいのか確かめなくてはならない。もし人1が人3は親切ではないとか、人0は親切だとかいう証言を持っていたら、この仮定は間違いだったと判明し、okがokじゃなくなる（Falseが入る）。

    for j in range(N):
        if(which_person[j]):

のように、こちらが正直かどうか決めつけた各人のことを見ていくが、もしwhich_person[j]が0ならそいつはどうでもよいので、次のjを見る。
which_person[j]が1だったら、よしこいつは本当に正直と仮定してよかったものかと実際にtestimonyを見なくてはならない。

もういちど整理しよう。
which_person[j]がというのはこちらの勝手な仮定、他方でtestimonyというのは仮定ではなく、実際に入力される証言である。ここで、testimony[j][k]がなんだったかというと、j番目の人がk番目の人に対してどう証言しているかということであった。
正直者である（はずの）j番目の人を固定して、じゃあ正直者なんだから言ってることに矛盾はないよなぁ？？？ってのを

            for k in range(N):
                #これ以降でj番目の人が正しいこと言ってるのか否かを調べてる。
                if testimony[j][k] == None: 
                    continue
                if testimony[j][k] != which_person[k]: #which_personってのは、全探索で仮定しているパターンの一つに過ぎない
                    ok = False

ここで確かめている。
各々の人を指すkのループを開始して、
j番目の人の証言であるtestimony[j][k]がもしNoneだったら、j番目の人はk番目の人に対して何も言ってないからスルー、
j番目の人の証言であるtestimony[j][k]がもし1とか0だったら、which_person[k]（こちらの仮定）と一致するかを確認。
which_personで例えば01010みたいに仮定してたら、kによってこの各bitを見ていくわけだけど、which_personで1ってなってるbit（つまり人）を0って証言していたり、0ってなってるところを1って証言していたりしたら、仮定が間違っていたと判断する。

他は説明略。

ans = 0の位置とか、一見すごく簡単そうにやってるところでも後からこのループの中に入ってなきゃだめだなとか考えて入れたりしたから、なかなか自分で書いてみないとピンとこない点は多い。