yukicoder : No.253 ロウソクの長さ

一ひねりが面白かったです。
http://yukicoder.me/problems/687

問題

長さXのロウソクがある。
最初の長さは10～10^9の範囲の整数である。

このロウソクの長さを当てたい。
そのため、現在のロウソクの長さがYと比べてどうであるか問い合わせるクエリを最大100回投げることができる。
１回クエリを投げると、その時点のロウソクの長さがYと一致・Y未満・Yを超える、のいずれであるかが得られる。
ただしクエリ応答後にロウソクの長さが1短くなる(0の場合それ以上短くならない)。

元の長さXを求めよ。

解法

二分探索で行うのがよさそう、というのはすぐに思いつく。
ただ、Xの上限は10^9なので、最大で30回位クエリを投げる必要が生じる。
ここで、Xが小さい場合、30回クエリを投げている間に長さが0になってしまう可能性がある。

よって、まず最初に100に近い値のクエリを投げてしまおう。
そこでロウソクの長さがそれより小さい場合、長さが0になるまで長さ0のクエリを繰り返せば、その回数で元の長さがわかる。

最初のクエリで、ロウソクの長さがそれより長いと返ってきたら、30回ぐらい二分探索してもロウソクは燃え尽きないので安心して二分探索しよう。
１回毎に長さが１短くなるのを忘れずに。

int ask(int Y){
	cout << "? " << Y << endl;
	int res;
	cin >> res;
	return res;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	x=ask(80);
	
	if(x==0) {
		cout << "! " << 80 << endl;
		return;
	}
	if(x<0) {
		for(i=2;i<=100;i++) {
			x=ask(0);
			if(x==0) {
				cout << "! " << i-1 << endl;
				return;
			}
		}
	}
	
	int L=80,R=1000000009;
	int num=1;
	while(L<R) {
		int M=(L+R)/2;
		
		x=ask(M-num);
		if(x==0) {
			cout << "! " << M << endl;
			return;
		}
		num++;
		if(x>0) L=M+1;
		else R=M;
	}
	cout << "! " << L << endl;
}

まとめ

ask関数を問題文中に書いてくれるのはありがたかったです。