cafelier@SRM

SRM460 250

あとで | 13:51 |

書いてみたら意外とTimeLimitシビアだった。

class TheQuestionsAndAnswersDivOne { public:
   int find(int questions, vector <string> answers) 
   {
      vector<int> Q(questions, -1);
      return rec(0, answers, Q, questions);
   }
   int rec(int i, const vector<string>& A, vector<int>& Q, int R)
   {
      if( R > A.size()-i ) return 0; // これ
      if( i == A.size() )  return 1;

      int cnt = 0;
      for(int q=0; q<Q.size(); ++q)
         if( Q[q] == -1 )
         {
            Q[q] = (A[i]=="Yes");
            cnt += rec(i+1, A, Q, R-1);
            Q[q] = -1;
         }
         else if( Q[q] == (A[i]=="Yes") )
         {
            cnt += rec(i+1, A, Q, R);
         }
      return cnt;
   }
};

この枝刈りがないと通らない。これは一発で気づけなくても自分を許せる気がしてきました。