紛らわしいけど、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、あんまりうまく解けないんだよな。