100問マラソン 4問目 SRM 663 Div2 Hard: CheeseRolling

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13919
優勝するトーナメントのパターン云々

解法

kmjpさんのを見させて頂きました．
TopCoder SRM 663 Div2 Hard CheeseRolling - kmjp's blog

#include <bits/stdc++.h>
using namespace std;

class CheeseRolling{
public:
	long long dp[16][1<<16];
	vector<long long> waysToWin(vector<string> wins){
		memset(dp,0,sizeof(dp));
		int n = wins.size();

		//一人の時に1を代入しておく
		for(int i=0;i<n;i++){
			dp[i][1<<n] = 1;
		}

		for(int mask=1;mask<1<<n;mask++){
			int bc = __builtin_popcount(mask);
			//2^i以外は必要ない
			if(bc & (bc-1) || bc == 1)continue;

			for(int mask2=mask;mask2>0;mask2=(mask2-1)&mask){
				int bc2 = __builtin_popcount(mask2);
				//部分集合を半分ずつの部分集合に分割
				if(bc*2 != bc)continue;
				int mask3 = mask ^ mask2;
				for(int x=0;x<n;x++) if(dp[x][mask2]) for(int y=0;y<n;y++) if(dp[y][mask3]){
					if(wins[y][x] == 'Y')
						dp[y][mask] += dp[x][mask2] * dp[y][mask3];
					else
						dp[x][mask] += dp[x][mask2] * dp[y][mask3];
				}
			}
			
		}

		vector<long long> ret;
		for(int i=0;i<n;i++){
			ret.push_back(dp[i][(1<<n)-1]);
		}
		return ret;
	}
};

理解は出来たが，今後活かせる程ではないのでもう少し考える．