Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

AOJ 1302 - Twenty Questions

問題文 : Twenty Questions

概要 :

長さ$m $ のビット列が$n$ 個ある. これらを一意に識別するために必要なビット数はいくらか?
ただし, あるビットの情報を得た後に次の戦略を考えても良い.

$1 \leqq m \leqq 11,\ 1 \leqq n \leqq 128$


解法 :
$rec[S]$ : ビットの状態が$S$ のグループを特定するのに必要なビット数の最小値, としてメモ化再帰. あるビットを指定したならそのビット(0 or 1), 指定していないならその情報(2) をもつので空間計算量は$O(3^m)$, 時間計算量は$O(mn3^m)$ である.

コード :

#include <cstdio>
#include <cstring>
#include <string>
#include <set>
using namespace std;

int m, n;
string s[128];
int rec[177147];
bool check[128];

int calc(int bit)
{
	if (rec[bit] >= 0) return (rec[bit]);
	
	int count = 0, nums = 0, mul = 0;
	
	for (int i = 0; i < n; i++) check[i] = true;
	
	for (int bits = 0; bits < m; bits++){
		mul = (mul == 0 ? 1 : mul * 3);
		if ((bit / mul) % 3 == 2) continue;
		nums++;
		for (int i = 0; i < n; i++){
			if (s[i][m - 1 - bits] - '0' != (bit / mul) % 3){
				check[i] = false;
			}
		}
	}
	
	for (int i = 0; i < n; i++) count += check[i];
	if (count <= 1) return (nums);
	
	int ret = m;
	mul = 0;
	for (int i = 0; i < m; i++){
		mul = (mul == 0 ? 1 : mul * 3);
		if ((bit / mul) % 3 != 2) continue;
		int nb = bit - 2 * mul;
		ret = min(ret, max(calc(nb), calc(nb + mul)));
	}
	
	return (rec[bit] = ret);
}

int main()
{
	while (scanf("%d %d", &m, &n) && n){
		
		for (int i = 0; i < n; i++){
			char buf[128];
			scanf("%s", buf);
			s[i] = (string)buf;
		}
		
		memset(rec, -1, sizeof(rec));
		
		int pow = 1;
		for (int i = 0; i < m; i++) pow *= 3;
		
		printf("%d\n", calc(pow - 1));
	}
	
	return (0);
}