TopCoderOpen 2015 Round2D Medium BallsInBoxes

無駄に難しく考えすぎた。二分探索まではたどり着いたのに。
http://community.topcoder.com/stat?c=problem_statement&pm=13969

問題

N個の箱が並んでおり、うち連続したK個にボールが入っていることが分かっている。
これらのK個のボールの位置を特定したい。

1つ箱を選んで開けることで、その箱のボールの有無が分かる。
最適な戦略を取る場合、最悪何個の箱をあければボールの位置を特定できるか。

解法

ボールがある左端の位置を特定すればよい、と考えるとその候補はN-K+1通り。

候補が2K個を超える場合、未調査の領域の端からK個目を開ける。
想定が最悪ケースなのでその箱はボールを含まないが、候補をK個減らすことができる。

候補が2K個以下になったら、後は二分探索で候補を絞ればいいので2^x≧(候補数)となる、x個の箱を開ければよい。

class BallsInBoxes {
	public:
	
	long long maxTurns(long long N, long long K) {
		ll cand = N-K+1;
		ll step = max(0LL, cand/K-1);
		cand -= step*K;
		
		for(int i=0;i<=60;i++) if(1LL<<i >= cand) return step+i;
	}
}

まとめ

こんなに簡単なコードになっちゃうのね。