TopCoder SRM 663 Div2 Hard CheeseRolling

割とオーソドックス。Div2Hardとはいえ900pt位で良くない？
http://community.topcoder.com/stat?c=problem_statement&pm=13919

問題

1～N番の選手N人(2の累乗)で行われるトーナメント戦がある。
N人中2人が直接対決したとき、どちらが勝つかを示したテーブルが与えられる。

N人から構成されるトーナメント表は、N!通り考えられる。
N!通りのうち、各選手が優勝するようなトーナメント表はそれぞれ何通りあるか。

解法

BitDPで、N人の部分集合からなるサブトーナメントにおいて、各人が優勝する組み合わせ数を更新していけば良い。

ll dp[1<<16][16];

class CheeseRolling {
	public:
	vector<long long> waysToWin(vector <string> wins) {
		int N=wins.size();
		int i,x,y;
		ZERO(dp);
		
		for(int mask=1;mask<1<<N;mask++) {
			int bc=__builtin_popcount(mask);
			if(bc&(bc-1)) continue;
			if(bc==1) {
				FOR(i,N) if(mask&(1<<i)) dp[mask][i]=1;
			}
			else {
				for(int mask2=mask;mask2>0;mask2=(mask2-1)&mask) {
					int bc2=__builtin_popcount(mask2);
					if(bc2*2!=bc) continue;
					int mask3=mask^mask2;
					FOR(x,N) if(dp[mask2][x]) FOR(y,N) if(dp[mask3][y]) {
						if(wins[y][x]=='Y') dp[mask][y] += dp[mask2][x]*dp[mask3][y];
						else dp[mask][x] += dp[mask2][x]*dp[mask3][y];
					}
				}
			}
		}
		
		vector<ll> V;
		FOR(i,N) V.push_back(dp[(1<<N)-1][i]);
		return V;
	}
}

まとめ

内容がトーナメント表だった記憶があるので、問題ページ開いた際に「CheeseRolling？」と頭にハテナが浮かんだ。