AIM Tech Round 5 : G. Guess the number

これは変わったインタラクティブ。
http://codeforces.com/contest/1028/problem/G

問題

1～10004205361450474の間のある整数xを当てるインタラクティブ問題である。
1回のクエリではK個の数値を指定すると、xがそれらに含まれるか、含まれない場合それらとの大小関係が返る。
これを最大5回用いてxを当てる。

しかし、K≦min(x,10000)でなければならない。

解法

以下の関数を考える。
f(L,Q) := xがL以上と確定しているとき、Q回クエリを実行すると[L,L+num(L,Q)]の範囲を特定できる
なお、L＞10000の場合はf(L,Q)=f(10000,Q)となる。

Q=1のとき、もう当てに行くしかないのでf(L,1)=L-1となる。
それ以外の場合を考えよう。
[L,L+f(L,Q-1)]までの範囲は残りのクエリで特定できるので、問い合わせるべきはL+f(L,Q-1)+1である。
同様に[L+f(L,Q-1)+2,L+f(L,Q-1)+2+f(L+f(L,Q-1)+2,Q-1)]の範囲は残りのクエリで特定できるので、次に問うべきはL+f(L,Q-1)+2+f(L+f(L,Q-1)+2,Q-1)+1である。
…という感じでmin(10000,L)個問い合わせる値を考えよう。

なお、この調子で考えていくと、5回のクエリで特定できる範囲はちょうど1～10004205361450474であることがわかる。

ll M[10101][10];
ll hoge=10004205361450474LL;

ll dp(ll L,int Q) {
	L=min(L,10000LL);
	if(M[L][Q]>=0) return M[L][Q];
	if(Q==0) return 0;
	if(Q==1) return L-1;
	
	ll la=L+dp(L,Q-1)+1;
	int i;
	FOR(i,L) la=la+1+dp(la+1,Q-1)+1;
	return M[L][Q]=la-L-1;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(M);
	ll L=1;
	int Q=5;
	while(1) {
		vector<ll> V;
		if(Q==1) {
			FOR(i,min(10000LL,L)) V.push_back(L+i);
		}
		else {
			V.push_back(L+dp(L,Q-1)+1);
			FOR(i,min(10000LL,L)-1) V.push_back(V.back()+1+dp(V.back()+1,Q-1)+1);
		}
		cout<<V.size()<<endl;
		FORR(v,V) cout<<v<<" ";
		cout<<endl;
		
		cin>>x;
		if(x==-1) return;
		
		if(x>0) L=V[x-1]+1;
		Q--;
	}
	
}

まとめ

言われてみると簡単だがややこしい。