yukicoder : No.753 最強王者決定戦

こちらの方がシンプルかな。
https://yukicoder.me/problems/no/753

問題

16人で勝ち抜き方式のトーナメント戦を行う。
入力として、互いに1対1で試合をしたときどちらが勝者になるかが与えられる。

トーナメントの並び順16!通りのうち、各人が優勝する組み合わせの数を求めよ。

解法

下記を考える。
f(A,mask) := maskで構成されるbitcount(mask)人のトーナメントのうちAが勝利する組み合わせ
求めたいのはf(*,2^16-1)である。

f(A,mask)とf(B,mask') (maskとmask'のbitcountが同じ)がわかっている場合、２つのトーナメントの勝者同士が戦うとすると
f(C, mask | mask') += 2*f(n,mask)*f(n',mask') (CはAとBの勝者)
とDPできる。２倍するのは左右どちらに両トーナメントが来る場合も結果が同じためである。

int N;
int A[16][16];
ll win[16][1<<16];
vector<int> C[1<<16];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	N=16;
	FOR(y,N) FOR(x,N) {
		cin>>A[y][x];
		if(A[y][x]==0) A[y][x]=-A[x][y];
	}
	
	FOR(x,N) win[x][1<<x]=1;
	FOR(i,N) FOR(j,1<<N) if(j&(1<<i)) C[j].push_back(i);
	
	for(int mask=1;mask<1<<N;mask++) if(__builtin_popcount(mask)%2==0) {
		FOR(x,N) if(mask&(1<<x)) break;
		for(int sub=mask; sub>0; sub=(sub-1)&mask) if((sub&(1<<x)) && __builtin_popcount(sub)*2==__builtin_popcount(mask)) {
			int oth=mask^sub;
			FORR(a,C[sub]) FORR(b,C[oth]) {
				if(A[a][b]>0) win[a][mask]+=2*win[a][sub]*win[b][oth];
				if(A[a][b]<0) win[b][mask]+=2*win[a][sub]*win[b][oth];
			}
		}
	}
	
	FOR(i,N) cout<<win[i][(1<<N)-1]<<endl;
	
}

まとめ

どこかで出ていそうな問題ではあるけども。