AOJ1302 Twenty Questions

コンテスト後の懇親会での議論を思い出しながら書いてみた。

Source

ACM/ICPC Asia Regional 2009 Tokyo Site: Problem H

解法

{ objectの部分集合 => 最適解 }をメモ再帰で求める。部分集合なので状態数は一見して最大 2^N (N = 128) になりそうだけど、質問を基準に考えると 2^M (M = 11) 程度にしかならないことがわかる。
まさかこんなに簡単に書けるとは思わなかった。Bより簡単だ！

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#define REP(i,e) for(int i=0;i<(int)(e);i++)
using namespace std;

typedef vector<int> vint;

enum{ N=128, M=11 };

int n,m;
char v[N][M];
map<vint,int> ans;

int rec(vint& t){
  if(t.size()==1) return 0;
  if(!ans.count(t)){
    int res=1<<20;
    REP(j,m){
      vint a,b;
      REP(i,t.size()) v[t[i]][j]=='0' ? a.push_back(t[i]) : b.push_back(t[i]);
      if(!a.empty()&&!b.empty()) res=min(res,max(rec(a),rec(b))+1);
    }
    return ans[t]=res;
  }
  return ans[t];
}

int main(){
  while(cin >> m >> n && n|m){
    REP(i,n) REP(j,m) cin >> v[i][j];
    vint t(n);
    REP(i,n) t[i]=i;
    ans.clear();
    cout << rec(t) << endl;
  }
}