kmjp's blog

競技プログラミング参加記です

Codeforces ECR #087: G. Find a Gift

紛らわしいけど、ECR087を1つ書き忘れてた。
https://codeforces.com/contest/1354/problem/G

問題

N個の箱があり、うちK個は価値のあるアイテムが入っている。KはNの半分以下である。
価値のあるアイテムがない箱はいずれも同じ重さで、アイテムが入っている箱より重い。
アイテムが入ってる箱は重さがばらついている。

2つの箱の集合を指定すると、どちらの集合の総和が重いかわかるクエリを50回まで用いて、価値あるアイテムの入っている最小の箱番号を求めよ。

解法

まず、1番にアイテムが入っているか判定する。
乱択で30回ほど箱を選び、1番と比較しよう。
もし1番にアイテムが入っているなら、半分以上の確率で1番の方が軽いと判定されるので、1/2^30以下の確率でしか漏らさない。

1番にアイテムがない場合、倍々ゲームの要領で、アイテムが入っている区間を絞ろう。
今[1,a]にアイテムがないことがわかっている場合、[1,a]と[a+1,2a]を比較すれば[a+1,2a]にアイテムがあるかわかる。
確実にアイテムがある区間を求めたら、今度は半々に絞りこんでいけばよい。

int T,N,K;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	srand(time(NULL));
	cin>>T;
	while(T--) {
		cin>>N>>K;
		
		FOR(i,30) {
			x=rand()%(N-1)+2;
			cout<<"? 1 1"<<endl;
			cout<<1<<endl;
			cout<<x<<endl;
			cin>>s;
			if(s=="SECOND") {
				cout<<"! 1"<<endl;
				break;
			}
		}
		if(i<30) continue;
		
		int len=1;
		while(2*len<=N) {
			cout<<"? "<<len<<" "<<len<<endl;
			FOR(i,len) cout<<i+1<<" ";
			cout<<endl;
			FOR(i,len) cout<<i+1+len<<" ";
			cout<<endl;
			cin>>s;
			if(s=="FIRST") {
				break;
			}
			assert(s=="EQUAL");
			len*=2;
		}
		
		int tl=min(len,N-len);
		for(i=9;i>=0;i--) if(tl>1<<i) {
			cout<<"? "<<(tl-(1<<i))<<" "<<(tl-(1<<i))<<endl;
			FOR(j,(tl-(1<<i))) cout<<1+j<<" ";
			cout<<endl;
			FOR(j,(tl-(1<<i))) cout<<1+j+len<<" ";
			cout<<endl;
			cin>>s;
			if(s=="FIRST") {
				tl-=1<<i;
			}
		}
		
		cout<<"! "<<len+tl<<endl;
		
		
		
	}
}

まとめ

乱択使うinteractive、あんまりうまく解けないんだよな。