ABC147 C HonestOrUnkind2

問題

atcoder.jp

N人の正直者（必ず本当のことを言う）か不誠実な人（本当のことを言うかわからない）がいる。N人の人が〇〇さんは正直者（または不誠実な人）だよと証言する。証言が矛盾しない範囲で，最大で何人の正直者がいるかを求めよ。

試行錯誤（全探索に至るまで）

問題を読み，入出力の例を見て厳しいなと思ってしまうような印象。で，少し考えてもわからない。一人一人の証言を確認していけば，判断できるけどそれを実装する方法がわからないなー，という感じ。

それで困ってしまって，D問題を見たり，順位表を眺めたりなどして考えるふりをしていた。でもしばらくしてまた順位表をみたらＣ問題が解けている人が少なそうだったので，これ解けたらパフォ少しは出るんじゃね？と思ってもう少し頑張ることにした。

入力の制約を改めて確認すると となっており，ん？これ全探索で行けるのでは，と感じました。N人の人はそれぞれ正直者（１）または不誠実（０）のいずれかなので， 通りで全部である。がどれくらいかよくわからなかったので，計算したらだったので，余裕そうである。

試行錯誤（全パターンの生成）

全探索するという方針が固まったので，全パターンをどうやって列挙するかを考えることにした。正直者が１，不誠実が０なのでみたいな感じの列が作れればＯＫということがわかった。以前のABCの問題で組み合わせの全列挙をやったことがあったので，それを利用しようと考えた（結果的にこれは不要，より道であった）。

atcoder.jp

これではだめそうだったので，ググったところ以下の記事が見つかったので，参考にしてみた

note.nkmk.me

これを利用してももちろんできるのだが，全パターンがだし，bit使えばできるんじゃね？ということに試行錯誤しているうちに気が付いた（今回のABCのD問題をちらちら見ていたのも良かったのかもしれない）。

atcoder.jp

実装

無事bitで実装すれば良さそうということに気づいたが，この段階で22時30分頃。一発でバグなしで実装できればぎりぎり間に合うかもしれないという感じ （結果として，長特急で実装しましたが，1WA, 2REでダメでした）。

ちなみに，全探索して正直者をカウントするところの実装はこんな感じ

for h in H:
    cnt = h.count("1")
    for ixy in IXY:
        i,x,y = ixy[0],ixy[1]-1,ixy[2]
        if h[i] == "1" and h[x] != str(y):
            cnt = 0
            break
    ans = max(ans,cnt)

hには100001111101010みたいな列が全パターン格納されている。 とりあえずこれで細かい修正を（ほかの部分に）してコンテスト後にちゃんとACをとったコードがこちら

N = int(input())

#人が一人しかいないとき
if N == 1:
    print(1)
    exit()

#人が2人以上いるとき
#N人それぞれが正直か不誠実かの全パターンを生成
H = []
for i in range(2**N):
    S = str(bin(i))
    H.append(S[2:].zfill(N))
#入力を受け取る
IXY = []
for i in range(N):
    t = int(input())
    for j in range(t):
        x,y = map(int,input().split())
        #i番目の人が「x番目の人はyである」と証言
        IXY.append([i,x,y])

ans = 0
for h in H:
    cnt = h.count("1")
    for ixy in IXY:
        i,x,y = ixy[0],ixy[1]-1,ixy[2]
        if h[i] == "1" and h[x] != str(y):
            cnt = 0
            break
    ans = max(ans,cnt)
print(ans)

ただ，人数をカウントするところなど，結局bit演算を全く活用していないので，その部分は勉強してあとから書き直そうと思っています。 参考になりそうな記事は以下。

qiita.com