2002/Contest/金沢大会

Problem G : True Liars †

問題概要 †

p1 人の正直者と p2 人の嘘つきがいる。人物 i に「人物 j は正直者か」という質問をしたときの回答が与えられたとき，誰が正直者で誰が嘘つきかを判定して正直者の一覧を出力する。判定できなければ「no」と出力する。

解法 †

次を手がかりとして，p1 人の部族と p2 人の部族に分ける。なお，p1 と p2 が等しいときは常に判断不能（どちらの部族が正直者で，どちらの部族が嘘つきかわからないから）。

• 人物 i に「人物 j は正直者か」と質問したときに「yes」という回答が得られたときは i と j は同じ部族に属す。
• 同様に「no」が得られたときは i と j は異なる部族に属す。

プログラミング・プロムナード 2003年5月号

議論・その他 †

• 泉は何らかの方法で解いたらしいがプログラムが複雑怪奇でよくわからない。（泉，18 Apr 2004）
• プロムナードの内容をほぼ忠実に実装。多分、これで正解だと思うんだけど...。（三廻部，19 Jun 2004）
• ところで、「泉は何らかの方法で解いたらしいがプログラムが複雑怪奇でよくわからない。」 ...??? （三廻部，19 Jun 2004）
• たぶん 2004/04/18 のプログラムは誤り。プロムナードに掲載されているコードの断片を流用して C 言語のプログラムを作成したところ，三廻部の出力と一致。したがって，少なくとも三廻部の実装が間違っていることはないはず。（泉，25 Jun 2004）
• 最初の分類の部分に誤りを発見。修正版で出力が一致したので，接頭辞の mikurube_ をとって正式版にします。（泉，26 Jun 2004）
• はじめまして。あまり自信がないのですが、liar_out.txtの最後の答えが間違っている気がします。確認用Pythonスクリプトをocean_confirm.pyとして添付します。（スクリプト中の 's' に列挙されているのがあるべき答え・・・だと思います） -- ocean? 2007-05-03 (木) 13:01:35
• 蛇足ですが、拙作の回答スクリプトをliar.pyとして添付します。 -- ocean? 2007-05-03 (木) 13:02:33

ファイルを添付する †

ocean_liar.py

ocean_confirm.py

liar.txt

frankdock_WA_G2.c

frankdock_WA_G.c

liar_out.txt

mikurube_G.cpp