CSAcademy Round #58 : D. Tournament Swaps

Dで苦戦しすぎて微妙な結果に。
https://csacademy.com/contest/round-58/task/tournament-swaps/

問題

2^N人のトーナメント表と、相対的な(2^N)人の強さが与えられる。

各参加者について、自身と他人の位置を１回だけswapできる場合、最大何回勝利できるか答えよ。

解法

強い順位処理していく。
トーナメント表をヒープとみなし、根から幅優先探索順で番号を振っていたっと考えよう。
自身の最大勝利数は、到達可能な範囲で最も小さい番号の頂点で決まる。

あとは到達可能な範囲を考えるだけである。
自身および自身より強い人に関し、それぞれ対応する頂点から根頂点までさかのぼり、各頂点のカウンタを+1していったと考えよう。
カウンタが2以上ということは、そこに到達可能性がある自身より強い人が２人以上いることになるので、1回swapしても到達できない。
言い換えればカウンタが1以下の頂点番号のうち最も小さい番号が到達可能な点である。

後はsetとか使いカウンタが1以下の集合を管理すればよい。
以下のコードは本番色々考えていたのでだいぶ冗長なコードになっている。

int T;
int N;
int A[1<<18];
int S[1<<18];
int R[1<<18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		set<int> S0,S1;
		cin>>N;
		FOR(i,1<<N) cin>>A[i+1],R[A[i+1]]=i+1;
		for(i=1;i<2<<N;i++) S0.insert(i);
		FOR(i,2<<N) S[i+1]=0;
		
		vector<int> ret;
		for(i=1<<N;i>=1;i--) {
			
			int highest=*S0.begin();
			
			x = R[i]+(1<<N)-1;
			while(x>=1) {
				if(S[x/2]) {
					S1.erase(x/2);
					break;
				}
				x/=2;
				S[x]=i;
				S0.erase(x);
				S1.insert(x);
			}
			
			x/=2;
			while(x>=1) {
				S1.erase(x);
				x/=2;
			}
			S1.erase(0);
			
			if(S1.size()) highest=min(highest,*S1.begin());
			
			y=0;
			while(highest>=1<<y) y++;
			ret.push_back(N+1-y);
		}
		FOR(i,1<<N) _P("%d%c",ret[(1<<N)-1-i],(i==(1<<N)-1)?'\n':' ');
		
	}
}

まとめ

落ち着いて考えれば非常に簡単な解法だが、本番だいぶ手こずってしまった。