mayoko’s diary

プロコンとかいろいろ。

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;
	}