Codeforces ECR #113 : E. Playoff Restoration

本番test case46で落としてる…。
https://codeforces.com/contest/1569/problem/E

問題

2^Kチームで勝ち抜きトーナメントを行うことを考える。
各チームiの順位がP[i]であるとき、ハッシュ値を整数Aを用いてsum(i*(A^P[i])) % 998244353で定める。
ハッシュ値が与えられたとき、それに合致する各チームの順位一覧があるなら1例を示せ。

解法

半分全列挙で行う。

f(n, k) := n番の選手がk回目まで勝ち抜いた場合の、そこまでのハッシュ値の集合
として、愚直にハッシュ値一覧を計算しよう。
最大で32名のトーナメントなので、前半後半それぞれ2^15通りの試合結果を総当たりすればよい。

前半半分のトーナメントのハッシュ値を総当たりすれば、後半半分のトーナメントのハッシュ値が確定するので、そのようなケースが存在するかわかる。
あとは前半後半それぞれDP復元すれば解。

int K;
ll A[55];
ll H;
const ll mo=998244353;
int ret[32];
unordered_map<int,pair<ll,ll>> memo[6][33];

void dfs(int level,int cur,int h) {
	if(level==0) return;
	auto v=memo[level][cur][h];
	int x=v.first>>32;
	int h1=v.first%(1LL<<30);
	int y=v.second>>32;
	int h2=v.second%(1LL<<30);
	
	if(ret[x]==0) ret[x]=1+(1<<(K-level));
	if(ret[y]==0) ret[y]=1+(1<<(K-level));
	
	dfs(level-1,x,h1);
	dfs(level-1,y,h2);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>A[1]>>H;
	A[0]=1;
	for(i=2;i<=50;i++) A[i]=A[i-1]*A[1]%mo;
	
	FOR(i,1<<K) {
		memo[0][i][0]={};
	}
	FOR(i,K) {
		FOR(y,1<<K) FOR(x,1<<K) {
			if((y>>(i+1)!=x>>(i+1))) continue;
			if((y>>i)==(x>>i)) continue;
			
			FORR2(h1,v,memo[i][x]) {
				FORR2(h2,v2,memo[i][y]) {
					ll h=h1+h2+(y+1)*A[(1<<(K-i-1))+1];
					pair<ll,ll> V={((1LL*x)<<32)+h1,((1LL*y)<<32)+h2};
					memo[i+1][x][h%mo]=V;
				}
			}
		}
	}
	FOR(i,1<<K) {
		ll h=(H+mo-(i+1)*A[1]%mo)%mo;
		
		if(memo[K][i].count(h)) {
			ret[i]=1;
			dfs(K,i,h);
			FOR(j,1<<K) cout<<ret[j]<<" ";
			cout<<endl;
			return;
			
		}
		
		
	}
	cout<<-1<<endl;
}

まとめ

半分全列挙に気付けるかが鍵。