折りたたみを展開する

おぼえ書き、まとめ、発表など

アルゴリズムパズル

毒飲ましゲーム

随分物騒な題名だが、アルゴリズムに関連したパズル問題には、毒が良く出て来る。大抵は奴隷と  n 個のコップがが出てきてその大抵が毒入りなのだ。大抵の質問は、効率的にアタリを見つけるには?とかそんなの。

f:id:Rlan:20170619001428p:plain

f:id:Rlan:20170619001432p:plain

ということで、今回も毒飲ましゲームにしよう。あなたは被験者で、 n 個の解毒剤を持っている。1個当たりには、同量の解毒作用が入っている。幸運なことにあなたは k 人の被験者がいる。 被験者には毒を飲んでもらい、適当な量の解毒剤(  0 \leq m \leq n )を飲んでもらう。もし、解毒剤の量が足りなければ被験者には症状が出る。あなたは、必要な解毒剤の量を効率的に調べたい。

考え方

さて、どの程度の効率性を達成するかは解毒剤の量に依存している。例えば、解毒剤が  k=n 個であれば、1錠づつ毒薬を増やして飲んでおけば良い。最悪の、ちょうど  n 個目で解毒効果が発揮されるケースでも対応することができる。だがもし、被験者が  log_2(n) 人いれば二分探索を実行できる。

具体的な問題

ここで、あなたは2人の被験者がいるとしよう。どうすれば効率良く、最小の解毒剤の量を見つけることができるだろうか。