SRM 460 250pt: TheQuestionsAndAnswersDivOne

TopCoder

問題概要

質問がQ(<=9)問存在する。全ての質問が最低1回は行われた。回答のリストがN(<=9)個与えられる。同じ質問には同じ回答がなされている。可能な質問の順番は何通りあるか求める問題。

考えたこと

  • 解けそうで解けない。制限が小さいから全探索っぽいことをするんだろうけど。
  • yesと答えた質問がいくつあるか、を固定すれば場合の数に落ちそう。
  • でもこれは何度も考えてその度に解けなかったやつだ。
  • 具体的には、N個のボールをK色のいずれかで塗る。ただしどの色も最低1回は使っている。そのような組み合わせは何通りあるか。
  • 包除原理使えば一応出せると思うけど、包除原理とか間違えやすいので書きたくない。
  • なので組み合わせ的な考えは最後の手段として置いておき、ビットDPの解法を考える。
  • 状態を(i番目の質問、どの質問がyesか、どの質問が既に使われたか)でいけそう？
  • これだと(どの質問がyesか)っていうのは独立なので外に出せる(出さなくても別にいいけど)。
  • なので、どの質問がyesか固定した状態で(i番目の質問、どの質問が既に使われたか)でDP行ける。
  • 書けた。サンプル通らない。何で？
  • NとQ間違えてたというかQ使って無かった。修正して提出。無事通った。

practiceで通ったコード

計算量O(N * Q * 2^(2*Q))。

#include <vector>
#include <string>
#include <cstring>
using namespace std;

const int MAX_N = 9;
int dp[MAX_N+2][1<<MAX_N];

struct TheQuestionsAndAnswersDivOne {

	int find(int questions, vector <string> answers) {
		const int N = answers.size();

		int ret = 0;
		for(int is_yes=0; is_yes<(1<<questions); is_yes++){
			memset(dp, 0, sizeof(dp));

			dp[0][0] = 1;
			for(int i=0; i<N; i++){
				bool yes = answers[i] == "Yes";
				for(int bit=0; bit<(1<<questions); bit++){
					for(int j=0; j<questions; j++)if( yes ^ !((is_yes>>j)&1) ){
						dp[i+1][bit | (1<<j)] += dp[i][bit];
					}
				}
			}

			ret += dp[N][(1<<questions)-1];
		}

		return ret;
	}

};