naoya_t@topcoder

SRM460 Easy: TheQuestionsAndAnswersDivOne

過去問 | 17:10 |

全パターン試すのそんなに難しくないし…

まあ目が覚めてて落ち着いてれば解ける問題でした。

#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

int fact(int x)
{
  int val = 1;
  for (int i=x; i>1; i--) val *= i;
  return val;
}

class TheQuestionsAndAnswersDivOne {
  int qn,an;
  vector<int> ans,pat;

  bool match() {
    vector<int> d(qn,-1); //毎回allocateするのどうよ
    rep(i,an){
      int q = pat[i], a = ans[i];
      if (d[q]<0) d[q]=a;
      else if (d[q]!=a) return false;
    }
    return true;
  }
  int test(int qi,int ai) {
    int cnt=0;
    if (qi==qn) {
      if (ai<an) return 0;
      // vector<int> t(all(pat));
      do {
        if (match()) cnt++;
      } while(next_permutation(all(pat)));
      return cnt;
    } else {
      int qr = qn - qi;
      int ar = an - ai, rest = ar - qr;
      for (int c=1;c<=1+rest;c++) {
        for (int i=ai;i<ai+c;i++) pat[i]=qi;
        cnt += test(qi+1,ai+c);
      }
      return cnt;
    }
  }
 public:
  int find(int questions, vector <string> answers) {
    qn=questions, an=sz(answers);
    if (qn==an) return fact(qn);
    ans.resize(an); rep(i,an) ans[i]=(answers[i]=="Yes")?1:0;
    pat.assign(an,-1);
    return test(0,0);
  }
};

• passed system test