yukicoder : No.1937 Various Tournament

これは割かしストレートな問題。
https://yukicoder.me/problems/no/1937

問題

N人(Nは2の累乗)からなる勝ち抜き戦を考える。
特定の2人が戦ったとき、どちらが勝つかという表が与えられる。

勝ち抜き戦の対戦表N!通りのうち、各人が勝つ組み合わせは何通りかを求めよ。

解法

BitDPで解く。
f(mask, k) := maskに対応する参加者のうち、k番の人が勝つ組み合わせ
とすると、
f(mask,x)とf(mask’,y)より、win(x,y)をx番とy番のうちの勝者とすると、
f(mask | mask' , win(x,y)) += f(mask,x)*f(mask',y)
のように状態遷移できる。

int N;
int W[16][16];
ll win[1<<16][16];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) FOR(x,N) cin>>W[y][x];
	
	FOR(i,N) win[1<<i][i]=1;
	int mask;
	FOR(mask,1<<N) {
		k=__builtin_popcount(mask);
		if(k<2||k&(k-1)) continue;
		for(int sm=mask;sm>=0;sm--) {
			sm&=mask;
			y=__builtin_popcount(sm);
			if(y*2!=k) continue;
			int lef=mask^sm;
			FOR(x,N) if(lef&(1<<x)) {
				FOR(y,N) if(sm&(1<<y)) {
					if(W[x][y]) {
						win[mask][x]+=win[lef][x]*win[sm][y];
					}
					else {
						win[mask][y]+=win[lef][x]*win[sm][y];
					}
				}
			}
			
		}
	}
	FOR(i,N) cout<<win[(1<<N)-1][i]<<endl;
	
}

まとめ

勝ち抜きトーナメントに関する問題、今まで何問ぐらいあったかな。