aoj1302:Twenty Questions

問題文

Twenty Questions | Aizu Online Judge

解法

各桁について、「未質問」「質問したら1だった」「質問したら0だった」の3通りの状態がありうる。
M<=11なので、O(3^M)は十分に現実的。

よって、いい感じにメモ化再帰を行うことで幸せになる。

コード

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int en(vint &v){
    int ret=0;
    rep(i,v.size()){
        ret=ret*3+v[i];
    }
    return ret;
}


int M,N;

int memo[81*81*27];
int dfs(vint lis,vint v){
    int c=en(v);
    if(memo[c]!=-1)return memo[c];

    if(lis.size()==1)return 0;
    int &ret=memo[c];
    ret=1001001001;
    rep(i,M){
        bool ok=false;
        rep(j,lis.size())if((lis[j]>>i&1)!=(lis[0]>>i&1))ok=true;
        if(!ok)continue;
        vint x,y;
        rep(j,lis.size()){
            if((lis[j]>>i&1))x.pb(lis[j]);
            else y.pb(lis[j]);
        }

        vint a,b;
        a=v;b=v;
        a[i]=1;b[i]=2;
        chmin(ret,max(dfs(x,a),dfs(y,b))+1);
    }
    return ret;
}

signed main(){
    while(cin>>M>>N,M||N){
        vector<int>lis;
        rep(i,N){
            string s;
            int b;
            cin>>s;
            rep(j,s.size()){
                b=b*2+s[j]-'0';
            }
            lis.pb(b);
        }
        vector<int>v(M);
        memset(memo,-1,sizeof(memo));
        cout<<dfs(lis,v)<<endl;
    }
    return 0;
}