Algoogle

Algorithm for Programming Contest

AOJ 1302 Twenty Questions

Category: AOJ Tag: dp

Twenty Questions

問題概要


m桁のユニークなn個のビット列が存在する. ある桁のビットが立っているかどうかの質問を何回かしてn個のうちのどの数を指しているのかを当てたいとき, 最悪の場合の質問回数の最小を求めよ.

解法


memo[used][yn] := した質問usedに対して答えがynだったときのそれ以降の最悪の場合の最小の質問回数
でメモ化再帰する.
各objectとusedの積がそれぞれynに一致しているかどうかで残りの候補を数える.
1個以下だったらこれ以上質問はいらないので0を返す.

コード


(1302.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
int get_bin(){
    string s; cin >> s;
    int ret = 0;
    rep(i,s.size()) ret = ret*2+s[i]-'0';
    return ret;
}
int N, M, obj[128];
int memo[2048][2048];

int rec(int used, int yn){
    if(memo[used][yn] >= 0) return memo[used][yn];
    int cnt = 0;
    rep(i,M) if((obj[i]&used)==yn) cnt++;
    if(cnt < 2) return memo[used][yn] = 0;
    int ret = N;
    rep(i,N){
        int nu = used | (1<<i);
        if(nu == used) continue;
        ret = min(ret, max(rec(nu, yn|(1<<i)), rec(nu, yn))+1);
    }
    return memo[used][yn] = ret;
}

int solve(){
    memset(memo, -1, sizeof(memo));
    return rec(0,0);
}

bool input(){
    cin >> N >> M;
    rep(i,M) obj[i] = get_bin();
    return N or M;
}
int main(){
    while(input()) cout << solve() << endl;
    return 0;
}

Comments