AOJ 1302 Twenty Questions
問題
$n$ 個のものがあり，それらは $m$ 個の yes/no question の答えで区別できます． 適切な順番で質問したときに，$n$ 個全てを区別するのに必要な質問回数の最大値を最小化してください． 読解に苦労したけど，アキネイターですべての質問と答えが与えられたときに， 適切に質問して Yes/No の二分木の高さを最小化してくださいということ．
方針
最初に思いついた DP は「$dp[S][T] = S$ に含まれる質問でものを $T$ に絞り込めたとして，残りの質問回数の最小」とするもの．当然これの計算量は $O(2^n 2^m)$ で無理． しかし，集合 $S$ というのは陽に持たなくていい．なぜなら，すでにした質問の集合 $S'$ とその答え $T$ で復元できるから．「$dp[S’][T] = S'$ に含まれる質問の答えが $T$ である人を区別するのに必要な残りの質問回数の最小」としてメモ化再帰すると $O(2^{2m} n)$ で間に合う．
実装
#include <bits/stdc++.h>
using namespace std;
int m, n;
int ans[150];
int dp[2050][2050];
int rec(int asked, int answer){ // 聞かれた質問akedにanswerと答えた人たちを絞り込むときの答え
int &res = dp[asked][answer];
if(res != -1) return res;
res = m;
int rem = 0;
for(int i = 0; i < n; ++i){
if((ans[i] & asked) == answer){
++rem;
}
}
if(rem <= 1) return res = 0;
for(int i = 0; i < m; ++i){
if(asked >> i & 1) continue;
int cnt[2] = {};
for(int j = 0; j < n; ++j){
if((ans[j] & asked) == answer){
++cnt[ans[i] >> j & 1];
}
}
int tmp = 0;
for(int j = 0; j < 2; ++j){
tmp = max(tmp, 1 + rec(asked | 1<<i, answer | (j << i)));
}
res = min(res, tmp);
}
return res;
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
while(cin >> m >> n && m){
for(int i = 0; i < n; ++i){
char buf[100];
cin >> buf;
ans[i] = 0;
for(int j = 0; j < m; ++j){
if(buf[j]-'0') ans[i] |= 1 << j;
}
}
memset(dp,-1,sizeof(dp));
cout << rec(0,0) << endl;
}
}