C - HonestOrUnkind2(Python)

はじめに

atcoder.jp

ABC147のC問題、bit全探索を使うやつです。

今回は自分が競プロでいつも使っているC++でなく、 Pythonでやってみました。

実装

N = int(input())
g = [[-1]*N for i in range(N)] 　　　　#①i番目の人がj番目の人を正直もの(=1)といっているか、不親切(=0)といっているか、なにもいってない(=-1)か

for i in range(N):
    A = int(input())
    for j in range(A):
        a,x = map(int, input().split())
        a -= 1
        g[i][a] = x
ans = 0
for i in range(1 << N):
    d=[0]*N
    for j in range(N):
        if ((i>>j) & 1): 
            d[j] = 1
    ok = True
    for j in range(N):
        if d[j]: 　　　　　　　　　　　　#②正直者だと割り当てをした人を見る
            for k in range(N):
                if g[j][k] == -1: continue　
                if g[j][k] != d[k]: ok = False #③jの人の証言が、実際の割り当てとあっているかどうかを判断
    if ok:
        ans = max(ans, bin(i).count("1")) #④bitの数を数えて、ansと比較して大きい方をansに入れる
print(ans)

補足

① 入力通りに配列に入れるのではなく、後々に検証するために、誰が、誰に対してどのようなステータスを与えたのかを配列にしておく。
② bitが立っているインデックスに対応する人を正直者として、その人の証言を以降でチェックしていく
③ j番目の人のk番目の人に対する証言が、なければ(=-1であれば)次のループに入り、あればその証言が実際にd[k]と一致するかをチェックし、
一致していなかったら、j番目の人は正直ものでないので、ansへの代入の処理をしないようにする。
④ もし③で証言が実際にd[k]と一致していた場合、iで立っているbitの数を数えて、それとansを比較して大きい方をandに代入する。