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