技術室奥プログラミングコンテスト#4 Day1 : M - Pakenのうさぎ

これ本番後に落ち着いてるとできるけど、本番でやると混乱して手間取りそう。
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_m

問題

N(6000以下)個の飴のうち、当たり2個を当てるインタラクティブ問題である。
飴の連続した区間を指定すると、その中に当たりが2個ともあるかどうかを返すクエリがある。
このクエリを25回まで用いてあたりを判定せよ。

解法

区間[L,R)内に飴が2つあることがわかっているときに飴の位置の絞り方を考えよう。
まずL≦M≦Rにおいて[L,M)または[M,R)内のいずれかに2つ飴が固まってるか確認しよう。
どちらかに2つ固まっているなら、再帰的に[L,M)と[M,R)のどちらか飴が2つある方を処理していく。

どちらにも2つ飴が固まっていない場合、片方の飴は[L,M)、もう片方は[M,R)内にあることになる。
[L',R)内に飴があるようなL≦L'

int ask(vector<int> V) {
	cout<<"? "<<V.size();
	FORR(v,V) cout<<" "<<v;
	cout<<endl;
	string s;
	cin>>s;
	return s=="Rabbit";
}

void answer(int a,int b) {
	cout<<"! "<<a<<" "<<b<<endl;
	exit(0);
}

int N;


void hoge(int L,int R) {
	if(L+1==R) answer(L,R);
	vector<int> V;
	int i,x;
	int d=1;
	while(L+d*2<=R) d*=2;
	
	for(i=L;i<L+d;i++) V.push_back(i);
	if(ask(V)) hoge(L,L+d-1);
	V.clear();
	for(i=L+d;i<=R;i++) V.push_back(i);
	if(ask(V)) hoge(L+d,R);
	int M=L+d-1;
	
	int TR=M;
	for(i=12;i>=0;i--) if(TR+(1<<i)<R) {
		V.clear();
		for(x=L;x<=TR+(1<<i);x++) V.push_back(x);
		if(!ask(V)) TR+=1<<i;
	}
	TR++;
	int TL=M+1;
	for(i=12;i>=0;i--) if(TL-(1<<i)>L) {
		V.clear();
		for(x=TL-(1<<i);x<=TR;x++) V.push_back(x);
		if(!ask(V)) TL-=1<<i;
	}
	TL--;
	answer(TL,TR);
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	hoge(1,N);
	
}

まとめ

クエリ回数から、2回クエリを行うと半分に絞れる、ってのは予想着くよね。

二分探索を