SRM460 Div1 Easy(250) TheQuestionsAndAnswersDivOne

TheQuestionsAndAnswersDivOne

問題の把握に手間取った。

例えば、questions=2, answers={"Yes","No","Yes"}として、質問をQ1, Q2とすると、可能な質問の順番は
(Q1,Q2,Q1)
(Q2,Q1,Q2)
の２つ。(Q1,Q2,Q2)のような順番はQ2がYesにもNoにもなっているので不可。このような質問の順番が何通りあるかという問題。

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class TheQuestionsAndAnswersDivOne
{
    int questions;
    vector<int> answers;
    vector<int> ans;        //  i番目の質問の答え（-1で未決定）

public:
    int find( int questions, vector <string> answers );
    int BT( int d );
};

int TheQuestionsAndAnswersDivOne::find( int questions, vector <string> answers )
{
    this->questions = questions;

    this->answers.clear();
    for ( vector<string>::iterator a=answers.begin();
          a!=answers.end(); a++ )
        this->answers.push_back( *a=="Yes" ? 1 : 0 );

    ans.resize( questions, -1 );

    return BT( 0 );
}

int TheQuestionsAndAnswersDivOne::BT( int d )
{
    int n = (int)answers.size();

    //  答えの定まっていない質問の数は残りの深さ以下
    int u = (int)count( ans.begin(), ans.end(), -1 );
    if ( u > n - d )
        return 0;

    //  末端
    if ( d == n )
        return 1;
    
    //  この回で質問できるのはまだ訊いていない質問か答えが一致する質問
    int ret = 0;

    for ( int q=0; q<questions; q++ )
    if ( ans[q] == -1  ||  ans[q] == answers[d] )
    {
        int t = ans[q];
        ans[q] = answers[d];

        ret += BT( d + 1 );

        ans[q] = t;
    }

    return ret;
}