AOJ 1302 - Twenty Questions

大学の課題で当時解けなかったシリーズその2です(これで終わり)。
その1はこちら

Twenty Questions | Aizu Online Judge
提出コード
一言でいうならアキネーターです。
n種類の物を、m種類の質問(yes/noで答える質問です)で見分けるための最小手数を求めます。
質問の答えによって、その都度次にする質問の種類を変えることができます。


全探索でどれぐらいかかるのか調べてみます。
例えば、M=2とします。
現在判明している情報(0もしくは1)、および質問してない(?とします)、という3種類の組み合わせは
{00,01,0?,10,11,1?,?0,?1,??}
という9種類です。Mを一般化した場合でも、全体として通りにしかなりません。
つまり、上の通りの状態をメモし、そこになんらかの情報をのせておけば、Mは11以下であるため、メモ化再帰が使えそうです。
今回は、
「現在の状態のときにまだ残っている答えの候補から、唯一の答えを見つけ出すための最悪の質問回数」
を現在の状態とセットで記録します。
探索の方法について考えます。
初期の状態は??...???ですが、M種類の中から任意に1つ選び質問を行うと、 0もしくは1という2つの答えに分かれ、
??...0...???
??...1...???
という2種類のグループに分かれます。
グループを2つに分けたら、今度はその2つのグループに対して別々に何か質問をしていき、最終的に1つに絞れるまで繰り返していけば良いです。
質問はM種類あるので全てのパターンを試してみます。
候補が1つに絞れたとき、そこから「唯一の答えを見つけ出すための最悪の質問回数」はもちろん0になります。ここを基準にして、再帰の呼び出し元に戻るときに手数を1ずつ増やしていけば良いです。最後に、”最悪手数”が最小になるような質問の順番を決めて、そのときの回数を求めれば答えとなります。
メモは、現在残っている候補のグループをキーとし、そこから唯一の答えを見つけ出すための最悪手数を記録したマップを使用すると楽に書くことができます。
例によって少しやまさん(@yamasangamasan)の力をお借りしています(特に計算量のあたりです)