Codeforces #623 Div1 B. Double Elimination

ややこしい設定。
https://codeforces.com/contest/1314/problem/B

問題

2^Nチームで行われる大会があり、うち自分の好みのチームが複数指定される。
この大会は敗者復活戦ありのDouble elimination方式で行われる。

自分の好みのチームが登場する試合は最大何試合あるか。

解法

ある2人の対戦結果において、勝者・敗者それぞれが好みかどうかで4通りのバリエーションにおける、そこまでの好みのチームの最大登場試合数をマージしていこう。

4人からなる2つの対戦結果は、初戦勝者同士の勝敗、初戦敗者同士の勝敗、初戦勝者2試合目敗者と初戦敗者2試合目勝者の試合で計3試合が行われ、勝者側の勝者と敗者復活勝ち残りの2人の結果としてマージされる。

int N,K;
int A[1<<17];

vector<int> hoge(vector<int> L,vector<int> R) {
	vector<int> res(4,-1<<29);
	int i,j;
	FOR(i,4) FOR(j,4) {
		int w1=i/2,l1=i%2;
		int w2=j/2,l2=j%2;
		
		int p=L[i]+R[j]+(w1+w2>0)+(l1+l2>0);
		res[w1*2+w2]=max(res[w1*2+w2],p+(w2+l1+l2>0));
		res[w2*2+w1]=max(res[w2*2+w1],p+(w1+l1+l2>0));
		res[w1*2+l1]=max(res[w1*2+l1],p+(w2+l1+l2>0));
		res[w1*2+l2]=max(res[w1*2+l2],p+(w2+l1+l2>0));
		res[w2*2+l1]=max(res[w2*2+l1],p+(w1+l1+l2>0));
		res[w2*2+l2]=max(res[w2*2+l2],p+(w1+l1+l2>0));
	}
	return res;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,K) {
		cin>>x;
		A[x-1]=1;
	}
	
	vector<vector<int>> V;
	for(i=0;i<1<<N;i+=2) {
		if(A[i]+A[i+1]==2) {
			V.push_back({-1<<29,-1<<29,-1<<29,1});
		}
		else if(A[i]+A[i+1]==1) {
			V.push_back({-1<<29,1,1,-1<<29});
		}
		else {
			V.push_back({0,-1<<29,-1<<29,-1<<29});
		}
	}
	
	while(V.size()>1) {
		vector<vector<int>> V2;
		for(i=0;i<V.size();i+=2) {
			V2.push_back(hoge(V[i],V[i+1]));
		}
		swap(V,V2);
	}
	
	int ma=0;
	cout<<max({V[0][0],V[0][1]+1,V[0][2]+1,V[0][3]+1})<<endl;
	
	
}

まとめ

ちょっと説明が難しいな。