AtCoder Beginner Contest 147
C - HonestOrUnkind2
競プロというか論理パズルみたいな感じ
解法
全パターンを探索する。例えばN=3だったら[0,0,0], [0,0,1], [0,1,0], [0,1,1], [1,0,0], [1,0,1], [1,1,0], [1,1,1]
の8パターンにおいて証言と証言者の素性(正直者or不親切な人)に矛盾がないことを調べる。計算時間はO(2N)になるが、N<=15なので間に合う。
矛盾の有無判定は以下のようにして行う。
1. 正直者の証言だけを参考にする
2. 「xは正直者(1)である」「yは不親切な人(0)である」という証言を集めたものを{x:[1,...], y:[0,...], z:[...]}
の形で持つ
3. 人xの属性と、xに対して集まった証言(2.で作った辞書のkeyがxのvalue)を照らし合わせる
→key xがない(その人への証言がない)なら矛盾なし
→key xがあり、そのvalueの中身が全てxの属性と同じなら矛盾なし
→key xがあり、そのvalueの中身にxの属性以外が混じっていたら矛盾あり
人番号x | 属性(1 or 0) | 辞書 | 矛盾 |
---|---|---|---|
2 | 0 | key 2が存在しない | なし |
2 | 0 | {..., 2:[0,0,0], ...} | なし |
2 | 0 | {..., 2:[1,0,1], ...} | あり |
実装
全員のコメントを辞書で持つ。
ans=0 n=int(input()) comments={} for i in range(n): num=int(input()) comment=[] for j in range(num): comment.append(list(map(int,input().split(" ")))) comments[i]=comment
N人の属性の組み合わせ2N通りに対して全探索を行う。数字を一旦二進数に置き換えることで各人のパターンを表す数値文字列に変換できる。
for i in range(2**n): evidences={} people=list(str(format(i,'b').zfill(n))) #=>例) nが3でiが5の場合、peopleは['1','0','1']のようになる
いわゆるbit全探索です
各peopleに対して、属性が正直者(1)の場合のみ、その人のコメントを解法2.で述べた辞書(evidence)の形で持つ
for idx,person in enumerate(people): if person=='1': for comment in comments[idx]: evidences.setdefault(comment[0],[]).append(comment[1])
集まったevidenceに対して矛盾がないかどうかを解法3.で述べたフローに従って判定する。矛盾が一つもなければそのパターンにおける'1'の数を答えとしてもつ
conflict=False for key,value in evidences.items(): personality = int(people[key-1]) if value.count(personality) != len(value): conflict=True break if not conflict: ans=people.count('1')
ansは逐次大きい数に更新されるので、最後のansを出力すればよい
print(ans)
コンテスト結果
今回は全体的に難しめでした。
レート変化