TopCoder SRM 460 Div1 Easy TheQuestionsAndAnswersDivOne

問題

n種類の質問をした。
何回か同じ質問をしたかもしれないが、質問に対しては"Yes"または"No"の答えが返る。
それぞれの質問に対する答えが与えられるとき、質問の仕方は何通りあるか求めよ。

制約条件

n≦9
質問の個数≦9

方針

全探索による数え上げ。
ただし、そのままだとTLEするので枝刈りを入れる。

その時点で質問がn種類に達しないようならば、その時点で探索を打ち切る。
これで最悪ケースが300msくらいになる。

ソースコード

int n,m;
int cnt,ans[9];
bool q[9];
void rec(int c){
  if(c==m){
    rep(i,n)if(ans[i]<0)return;
    cnt++; return;
  }
  int rest=0;
  rep(i,n)if(ans[i]<0)rest++;
  if(rest>m-c)return;
  
  rep(i,n)if(ans[i]==-1||ans[i]==q[c]){
    int t=ans[i];
    ans[i]=q[c];
    rec(c+1);
    ans[i]=t;
  }
}
class TheQuestionsAndAnswersDivOne {
  public:
  int find(int questions, vector <string> answers) {
    n=questions;
    m=answers.size();
    rep(i,m)q[i]=answers[i]=="Yes";
    cnt=0;
    rep(i,n)ans[i]=-1;
    rec(0);
    return cnt;
  }
};