問題
http://community.topcoder.com/stat?c=problem_statement&pm=10768&rd=14146
解き方
数が小さいので全探索可能。
すでに答えた人の数、YesかNoかを答えたかの情報を持たせて
答えなくてもよい場合と答えなければならない場合についてDFSを用いる。
計算量がオーバーしてしまうので、途中で全員答えられないとわかった場合は
打ち切りを行う。
コード
int n,m;
int a[60];
class TheQuestionsAndAnswersDivOne {
public:
int rec(int num,int mask,int mask2){
if(m-num<n-__builtin_popcount(mask))return 0;
if(num==m)return 1;
int ret=0;
FORE(i,0,n){
if((mask&(1<<i)) && a[num]!=((mask2&(1<<i))!=0) )continue;
ret+=rec(num+1,mask|(1<<i),mask2|(a[num]<<i));
}
return ret;
}
int find(int questions, vector<string> answers) {
n=questions;
m=answers.size();
FORE(i,0,m)a[i]=(answers[i]=="Yes");
return rec(0,0,0);
}
};
int a[60];
class TheQuestionsAndAnswersDivOne {
public:
int rec(int num,int mask,int mask2){
if(m-num<n-__builtin_popcount(mask))return 0;
if(num==m)return 1;
int ret=0;
FORE(i,0,n){
if((mask&(1<<i)) && a[num]!=((mask2&(1<<i))!=0) )continue;
ret+=rec(num+1,mask|(1<<i),mask2|(a[num]<<i));
}
return ret;
}
int find(int questions, vector<string> answers) {
n=questions;
m=answers.size();
FORE(i,0,m)a[i]=(answers[i]=="Yes");
return rec(0,0,0);
}
};