割とオーソドックス。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?」と頭にハテナが浮かんだ。