AOJ 1302 Twenty Questions

問題

bitからなる異なる 個のbit列が与えられる。1回の質問でbitを1つ明らかにできるとき最悪でも何回の質問でbit列を1つに特定できるか求めよ。

問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1302

解法

まず前計算として、 cnt[S][T] = 質問したbitの集合がSでその結果がTであるようなbit列の個数、を求めます。TのSに含まれないbitは0としておきます。ここで であることに注目すればS,Tの組は部分集合の列挙の方法を用いて で調べ上げられます。

次に dp[S][T] = 質問したbitの集合がSでその結果がTであるときの最小回数、としてDPを行います。遷移はSに含まれない i bit目を質問したとして、最悪ケースを考えるため質問結果が0,1のときのmaxをとって dp[S][T] = max(dp[S|1<<i][T], dp[S|1<<i][T|1<<i])+1 のようになります。

計算量は になりました。

Code

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

constexpr int INF = 1 << 30;

void chmin(int &a, int b){
    a = min(a, b);
}

int cnt[1<<11][1<<11], dp[1<<11][1<<11];

int solve(){
    int m, n;
    cin >> m >> n;
    if(m==0) return 1;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        string s;
        cin >> s;
        for(int j=0;j<m;j++){
            a[i] |= (s[j]-'0')<<j;
        }
    }
    for(int S=0;S<1<<m;S++){
        for(int T=S;;T=(T-1)&S){
            cnt[S][T] = 0;
            dp[S][T] = INF;
            for(int i=0;i<n;i++){
                if((S&a[i])==T) cnt[S][T]++;
            }
            if(T==0) break;
        }
    }
    for(int S=(1<<m)-1;S>=0;S--){
        for(int T=S;;T=(T-1)&S){
            if(cnt[S][T]<=1){
                dp[S][T] = 0;
            }else{
                for(int i=0;i<m;i++){
                    if((S>>i)&1) continue;
                    chmin(dp[S][T], max(dp[S|1<<i][T], dp[S|1<<i][T|1<<i])+1);
                }
            }
            if(T == 0) break;
        }
    }
    cout << dp[0][0] << endl;
    return 0;
}

int main(){
    while(solve()==0);
    return 0;
}

コメント

bitの包含関係で頭を混乱させてしまったのでもっとスムーズに考察できるようにしたいです。