TopCoderOpen 2013 Round2C Hard WellTimedSearch

さてHard。
本番中には解けなかったけど面白い問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12515

問題

一列に並んだN個のセルのどこかに(均等な確率で)トークンが入っているので、それを探したい。
トークンを探すとき、２分探索の手順でセル絞りこんでいく。
プレイヤーが最適な戦略で２分探索の対象セルを選択するとき、数A,Bに対して、A回～B回の範囲でトークンの位置を特定できる確率を最大化し、その確率を答える。

解法

この問題を言い換えると、
「N要素からなる２分木を作って、深さA～Bに入る要素数を最大化させる」
となる。

A～Bの要素を最大化するには、Aの時点で十分な幅を持たせつつ、A以前の深さではできるだけ分岐する深さを深くすればよい。

N<=10^6と大きく、AやBも大きい。
ただ、2分木は深さが20もあれば2^20≒10^6個の要素が入るので、A～A+20の深さがあれば10^6個全要素入るので、大きすぎるBは必要ない。
また、A-20までの深さでは分岐を全くしなくても、Aの深さで幅を2^20にできる。

よってAの前後20だけ深さを考えればよい。
A以降はすべて２分岐してA～Bの数を最大化させ、A-20以下の深さは分岐をしなくてよい。
以下のコードでは、深さAの時点の幅Wを1～2^(A-1)に変化させたとき、深さA～Bの間に入る要素数を計算している。
深さA～Bの間にはW*(2^(B-A+1)-1)個の要素が入るので、N-(深さ(A-1)までの最小要素)とのうち小さい方が幅Wでの要素数となる。

この処理はO(N logN)なので、N<=10^6でも間に合う。

class WellTimedSearch {
	public:
	double getProbability(int N, int A, int B) {
		int ON=N;
		int i,j,k;
		if(A>20) {
			N -= (A-20);
			B -= (A-20);
			A -= (A-20);
		}
		B=min(B,A+23);
		
		ll ma=0;
		for(i=1;i<=1<<(A-1);i++) {
			ll tot2=0;
			k=A-1;
			j=i;
			while(j>1) {
				j=(j+1)/2;
				tot2+=j;
				k--;
			}
			tot2 += k;
			
			ll tn=i*((1<<(B-A+1))-1);
			//_P("%d %lld %lld\n",i,tn,N-tot2);
			ma=max(ma, min(N-tot2,tn));
		}
		return ma/(double)ON;
	}

};

まとめ

確率の問題が二分木構築になるのが面白い。
あと、Forumにある最短回答がすごすぎる…。