SRM 694 Div1 medium : DistinguishableSetDiv1

問題概要 :
n人にm回質問をする.
人と質問にはそれぞれ0からn-1,0からm-1まで番号が割り振られている.
人iの質問jに対する回答は英大文字('A'~'Z')として表現される.
各人の各質問への回答が入力として与えられる.
全ての人を区別するためにしなければならない質問の集合は何通りあるか.

解法 :
動的計画法

区別するためにしなければならない質問の集合を数え上げるのではなく、
区別できない質問の集合を数え上げる.

異なる2人を選び、その人らを区別できない最大の質問の集合を求める.
この集合は2人が同じ回答をした質問の集合である.
このような集合から1つ要素を取り除いた集合もまた区別できない質問の集合なので、
要素を取り除くことでそこから得られる区別できない質問の集合を全て列挙する.

あとはこれを全ての異なる2人に対して行えば良い.

本番は解けてないのでwriter解を見て解いた.
本番中は「Twenty Questionsっぽい問題だな〜」と考えていたけど、全く違った残念

コード :

bool dp[1<<20];

class DistinguishableSetDiv1 {
public:
  int count(vector <string> answer) {
    int n = answer.size();
    int m = answer[0].size();
    rep(i,n) REP(j,i+1,n) {
      int state = 0;
      rep(k,m) if( answer[i][k] == answer[j][k] ) state |= (1<<k);
      dp[state] = true;
    }
    int cnt = 0;
    for(int state=((1<<m)-1);state>=0;--state) if( dp[state] ) {
	rep(i,m) if( (state>>i) & 1 ) dp[state&~(1<<i)] = true;
      }
    rep(i,(1<<m)) cnt += dp[i];
    return (1<<m)-cnt;
  }
};