Google Code Jam 2013 Round 2 : B. Many Prizes

Bは最初手こずったものの、最終的にはきっちり解けて良かった。
https://code.google.com/codejam/contest/2442487/dashboard#s=p1

問題

0～(2^N-1)番からなる2^Nのチームでトーナメントを行う。
トーナメントでは、数字の小さい番号のチームが勝利する。

ここで、N回の試合の結果上位Pチームに商品が与えられる。
NとPが与えられたとき、以下を答えよ。

• トーナメントの組み合わせに寄らず、必ず商品を獲得できる最大のチーム番号
• トーナメントの組み合わせによっては、商品を獲得できる可能性のある最大のチーム番号

解法

本番は最初Pを２進数表記して、1のビットを動かしたりしたら求まらないかな？と思ったけどうまく行かなかった。
その後２分探索で解けた。

PをN桁の２進数表記をしたとき、上位ビットから順に0の位置に相当する試合は勝たないと上位Pチーム以上に入れない。
よって、A番のチームが必ず上位Pチームに入るかは次の様に求められる。

• 残ったチームのうち、Aより強いチームの数をWとする。
• 全N回の試合を順に見ていき：
  • 勝たないといけない試合でW>0なら負ける可能性があるので、A番は上位Pチームに入れない。
  • 勝たなくてもいい試合でW==0なら絶対勝つので、A番は上位Pチームに入れる。W>0の場合、自分より強い人は最大(W-W%2)/2人残る

A番のチームが上位Pチームに残る可能性があるか、は上記の処理をAより弱いチームの数に関して同様に行えばよい。
以下は似たような処理を２回書いているので長いが、Editorialでは非常にシンプルな回答が記載されている。

ll N,P;

int guaok(ll p) {
	int i;
	ll w=p;
	
	if(p>=(1LL<<N)) return 1;
	FOR(i,N) {
		if(P&(1LL<<(N-1-i))) {
			if(w==0) return 1;
			w=(w>>1)-1+(w%2);
		}
		else {
			if(w>0) return 0;
		}
	}
	return w==0;
}

ll gua() {
	int i;
	ll lo=0,hi=1LL<<N;
	
	FOR(i,N+3) {
		ll p=(lo+hi)/2;
		if(guaok(p)) lo=p;
		else hi=p;
	}
	
	for(lo=lo;lo<=(1LL<<N)-1;lo++) if(guaok(lo)==0) return lo-1;
	
	return (1LL<<N)-1;
}

ll couok(ll p){
	int i;
	ll l=(1LL<<N)-p-1;
	
	if(p>=(1LL<<N)) return 1;
	FOR(i,N) {
		if(P&(1LL<<(N-1-i))) {
			if(l>0) return 1;
		}
		else {
			if(l==0) return 0;
			l=(l>>1)-1+(l%2);
		}
	}
	return l==0;
}

ll cou() {
	int i;
	ll lo=0,hi=1LL<<N;
	
	FOR(i,N+3) {
		ll p=(lo+hi)/2;
		if(couok(p)) lo=p;
		else hi=p;
	}
	
	for(lo=lo;lo<=(1LL<<N)-1;lo++) if(couok(lo)==0) return lo-1;
	
	return (1LL<<N)-1;
}

void solve(int _loop) {
	int i,j,x,y,z,ne=0;
	
	cin>>N>>P;
	P--;
	ll xx=gua();
	ll yy=cou();
	
	_PE("Case #%d: %lld %lld\n",_loop,xx,yy);
}

まとめ

二分探索でいいことに気が付くまで少し時間がかかったが、ちゃんと解けて良かった。
おかげでTシャツはゲット。