mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ AOJ 問題 Twenty Questions | Aizu Online JudgeN 個の物体で構成された世界がある。これらすべては, M 種類の Yes/No で答えられる特徴で区別することができる。 あなたは, 今目の前にあるものがなんの物体であるかを調べたいのだが, 最悪の場合でもなるべく少ない質問回数で物体を判別したい。最悪の場合, 必要な質問回数を最小化せよ。ただし, 質問の答えを聞いてから次の質問を考えられることにする。 解法 普通に考えてみます。dp[S] = (解候補が S に絞られているとき, 最悪かかる質問回数の最小値) とします。M 個のうち適当な質問をすると, 「その質問に… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F07%2F16%2F171241" title="AOJ 1302 Twenty Questions - mayoko’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-07-16 17:12:41 rich https://mayokoex.hatenablog.com/entry/2016/07/16/171241 1.0 100%