Codeforces ECR #149 : E. Playoff Fixing

なんかボス問が妙に簡単だった回。
https://codeforces.com/contest/1837/problem/E

問題

2^K人の勝ち抜きトーナメントを考える。
(2^n+1)～(2^n)番の人は、残り2^n人の段階まで残るようにしたい。
今トーナメント表の一部が埋まっている場合、条件を満たす残りの埋め方は何通りか。

解法

トーナメントの下の方から、(2^n+1)～(2^n)番の人が入りうる場所を順次計算していけばよい。

int K,N;
int A[1<<20];
int rk[1<<20];
int num[22],fix[22];

int R[1<<20];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(R);
	scanf("%d",&K);
	
	x=0;
	for(i=1;i<=1<<19;i++) {
		if(i>(1<<x)) x++;
		rk[i]=x;
		num[x]++;
	}
	
	N=1<<K;
	
	FOR(i,N) {
		scanf("%d",&A[i]);
		if(A[i]!=-1) {
			A[i]=rk[A[i]];
			fix[A[i]]++;
		}
	}
	ll ret=1;
	FOR(i,K+1) {
		for(j=1;j<=num[i]-fix[i];j++) ret=ret*j%mo;
	}
	
	while(K>0) {
		FOR(i,1<<(K-1)) {
			x=A[i*2];
			y=A[i*2+1];
			if(x==-1&&y==-1) {
				ret=ret*2%mo;
				A[i]=-1;
			}
			else if(x==-1) {
				if(y==K) {
					A[i]=-1;
				}
				else {
					A[i]=y;
				}
			}
			else if(y==-1) {
				if(x==K) {
					A[i]=-1;
				}
				else {
					A[i]=x;
				}
			}
			else if(x>=K&&y>=K) {
				ret=0;
			}
			else if(x<K&&y<K) {
				ret=0;
			}
			else {
				A[i]=min(x,y);
			}
		}
		K--;
	}
	cout<<ret<<endl;
	
	
	
}

まとめ

そんなに難しくないはずだけど、なんか本番妙に手間取ってるな。