読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ1302 Twenty Questions

AOJ

SRM694Div1Med「Distinguishable」に似ていたので誤読をした(というより同じ問題だと思ってしまった.)

問題文

Twenty Questions | Aizu Online Judge
例によって日本語訳はないです.

解法

どんなオブジェクトも与えられた質問によって一つに特定できることが保証されているので,特定できるかどうかを心配する必要はないです.
というわけで,全探索をして解を探します.
適当に全探索をすると,O(n!2^n)みたいな感じでTLEになってしまいます.
冷静になると,今まで使った質問の順序は関係ないので,質問の結果が(まだ質問してない,yes,no)の3通りと考えると状態数が3^nになります.
なので,メモ化をすることでO(3^n)で解けます.

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1939651#1
コードでは質問の結果ではなく残ってる物体の候補の集合をbitに起こして管理しています.

それと,emacsで書いててインデントが崩れてた問題が解決した気がします.