AtCoder Regular Contest 078E: Awkward Response

http://arc078.contest.atcoder.jp/tasks/arc078_c

まず桁数を特定する。これは1, 10, 100,...と比較するとわかる。
それからは上の位から数字を特定していく。
例えば(10^3,10^4)の区間において49990を投げると、

(10^3,5*10^3)でyes,[5*10^3,10^4)でNoとなる。
同じようなことをにぶたんで行えば各桁が4回の質問で求められるので、64回の制限を余裕で満たす。

下のコードは自分でもわけのわからず通したもの…

bool ok(ll res) {
	//char c = get_ans(res);
	cout << "? " << res << endl;
	char c; cin >> c;
	return c == 'Y';
}


void solve() {
	ll res = 0;
	for(ll i = 0; i < 10; i++) {
		ll lv, rv = 10;
		if(i == 0) lv = 1;
		else lv = 0;
		while(rv - lv > 1) {
			ll m = (lv + rv) / 2;
			if(ok(res * 10 + m)) lv = m;
			else rv = m;
		}
		res = res * 10 + lv;
		//char c = get_ans(res + 1);
		cout << "? " << res + 1 << endl;
		char c; cin >> c;

		if((all_nine(res) && c == 'N') || (!all_nine(res) && c == 'Y')) {
			res -= 9;
			if(i == 0) lv = 0;
			else lv = -1;
			rv = 9;
			while(rv - lv > 1) {
				ll m = (lv + rv) / 2;
				if(ok(res * 10 + m * 10)) rv = m;
				else lv = m;
			}
			cout << "! " << res + rv << endl;
			return;
		}
	}
	cout << "!  1" << endl;
}

文字列を比較するときは文字の長さを特定するのも重要だね。