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)
コンテスト結果
今回は全体的に難しめでした。
レート変化
三井住友信託銀行プログラミングコンテスト2019
D. Lucky PIN
解法
取りうる暗証番号(000〜999)が可能かどうか1個ずつ全部調べる。
暗証番号の、
1桁目(百の位)の数字は、それがSで現れる最初の桁目でとる。これをa桁目とする。
3桁目(一の位)の数字は、それがSで現れる最後の桁目でとる。これをb桁目とする。
2桁目(十の位)の数字が、Sのa以上b未満の桁の範囲に現れれば、これをc桁目とする。
a,b,c桁目以外の数字をSから取り除くことでその暗証番号を得られる。
事前にSに現れる数字とその位置を{数字:[位置、位置、...], 数字:[位置、位置、...], ...}の形で持っておくことで計算時間を短縮する。
例)
3141592653589793238
=> {'3': [1, 10, 16, 18], '1': [2, 4], '4': [3], '5': [5, 9, 11], '9': [6, 13, 15], '2': [7, 17], '6': [8], '8': [12, 19], '7': [14]}
'892'はとれるか？
'8'=>[12, 19]=>12桁目でとる
'2'=>[7, 17]=>17桁目でとる
'9'=>[6, 13, 15]=>12より大きく17より小さい13(or15)桁目でとる
∴ とれる
実装
辞書を作る
n=int(input()) ls=list(input()) nums={} for idx,num in enumerate(ls): nums.setdefault(num,[]).append(idx+1) count=0
ゼロ埋めをもちいて000〜999に対して調べる。
for i in range(1000): i_zero=str(i).zfill(3) encrypt=list(i_zero)
1桁目(first)と3桁目(third)のとる位置を取得。2桁目の数字(second)がそれらの間からとれるかチェックして取れたらcount+=1
first_ls=nums.get(encrypt[0],[]) if not first_ls: continue first=first_ls[0] third_ls=nums.get(encrypt[2],[]) if not third_ls: continue third=third_ls[-1] second_ls=nums.get(encrypt[1],[]) for j in second_ls: if j>first and j<third: count+=1 break
print(count)
range(1000)のなかでsecond_lsをfor文で回してるためTLE臭がすごいけど、second_lsの長さもたかだか30000なのでギリギリ大丈夫だった。
forではなく二分探索で探せばもっとはやくできる。
コンテスト結果
レート変化
遅かったとはいえDまで解けたのに...
年内4桁いきてぇなぁ
