AOJ 1302 Twenty Questions
問題
Twenty Questions | Aizu Online Judge
N 個の物体で構成された世界がある。これらすべては, M 種類の Yes/No で答えられる特徴で区別することができる。
あなたは, 今目の前にあるものがなんの物体であるかを調べたいのだが, 最悪の場合でもなるべく少ない質問回数で物体を判別したい。
最悪の場合, 必要な質問回数を最小化せよ。ただし, 質問の答えを聞いてから次の質問を考えられることにする。
解法
普通に考えてみます。
dp[S] = (解候補が S に絞られているとき, 最悪かかる質問回数の最小値) とします。M 個のうち適当な質問をすると, 「その質問に Yes と答える集合」と「その質問に No と答える集合」に別れます。
この二つの集合を left, right として, dp[left] と dp[right] の最大値 + 1 が最小回数の答えになります。
ただ, 今のままだと S としてあり得るものが 2^N あり, こんな探索は不可能な気がします。しかし, 特徴は M 種類しかないので, グループの別れ方も 2^M 種類しかありません3^M でした(特徴を選んだことによる別れ方 2 通り + 特徴を選んでいない)。これを考えると, メモ化再帰をすれば上記の dfs で十分間に合うことがわかります。
int M, N; int character[150][15]; map<vi, int> mp; int dfs(vi S) { if (S.size() <= 1) return 0; int& ret = mp[S]; if (ret > 0) return ret; ret = M; for (int i = 0; i < M; i++) { vi left, right; for (int v : S) { if (character[v][i]) left.push_back(v); else right.push_back(v); } if (left.empty() || right.empty()) continue; ret = min(ret, 1+max(dfs(left), dfs(right))); } return ret; } int main() { while (cin >> M >> N) { if (M == 0 && N == 0) break; for (int i = 0; i < N; i++) { string s; cin >> s; for (int j = 0; j < M; j++) { character[i][j] = s[j] - '0'; } } mp.clear(); vector<int> S(N); for (int i = 0; i < N; i++) S[i] = i; cout << dfs(S) << endl; }