Codeforces #507 Div1 B. Subway Pursuit

言われてみれば解法は自明なんだけども。
http://codeforces.com/contest/1039/problem/B

問題

順に1～N番の番号が振られた線路上の電車の位置を特定するinteractive問題である。
クエリ１回では、ある連続区間を指定することで電車がその区間内にいるかどうかを得られる。
ただし、クエリ実行後、電車は最大K以下の範囲で近傍の駅に移動する。

解法

電車の移動は実質ランダムなので、確信をもって位置を当てることはできない。
幸いKはさほど大きくないので、ある程度範囲を絞って乱拓するしかない。

以下のコードでは以下の戦略を取っている。

• 確実にこの範囲にいる、区間[L,R]を管理しておく。
• 区間が4Kを超えるなら、二分探索で範囲を絞る。クエリ発行後にはいる可能性のある位置が2K広がるが、もともと4K以上の区間を取っているので確実に区間は狭まる。
• 区間が十分狭いなら乱拓。

ll N,K;

bool ask(ll L,ll R) {
	string S;
	cout<<L<<" "<<R<<endl;
	cout.flush();
	cin>>S;
	if(S=="Yes") {
		if(L==R) exit(0);
		return true;
	}
	assert(S=="No");
	return false;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	ll L=1;
	ll R=N;
	srand(time(NULL));
	while(1) {
		while(R-L>=45) {
			ll M=(R+L)/2;
			if(ask(L,M)) R=M;
			else L=M+1;
			R=min(R+K,N);
			L=max(L-K,1LL);
		}
		
		ll v=rand()%(R-L+1);
		ask(L+v,L+v);
		
		R=min(R+K,N);
		L=max(L-K,1LL);
		
	}
	
}

まとめ

これがなぜ思いつかないのか…。