コード結構長いな。
https://codeforces.com/contest/2129/problem/C3
問題
秘密の括弧列Sを特定するインタラクティブ問題である。
以下のクエリを100回まで用いて、Sを特定せよ。
Sのindexを指定し(同じindexを複数回使用してもよい)、S中の文字列を連結したT定める。
その時、f(T) := Tの連続部分列のうち正しい括弧列の数 を返す。
解法
g(n)を、C(g(n)+1,2)>C(g(1)+1,2)+...+C(g(n-1)+1,2) となるような数列とする。
以下のクエリを投げると、1クエリでSのうち12文字を特定できる。
(s[1]+")")*g(1)+")"+(s[2]+")")*g(2)+")"+...+(s[12]+")")*g(12)
int T,N; string S; string W; //="((())))())(())(())())(())(())())(())(())())(())(("; ll G[13]; int hoge(string A) { if(A.size()%2) return 0; int cur=0; FORR(a,A) { if(a=='(') cur++; else cur--; if(cur<0) return 0; } return cur==0; } int ask(vector<int> V) { if(W.size()) { string A; FORR(v,V) A+=W[v]; int i; int sum=0; int x,y; FOR(x,A.size()) for(y=1;x+y<=A.size();y++) sum+=hoge(A.substr(x,y)); return sum; } cout<<"? "<<V.size(); FORR(a,V) cout<<" "<<a+1; cout<<endl; int x; cin>>x; return x; } void solve() { int i,j,k,l,r,x,y; string s; G[1]=1; for(i=2;i<=12;i++) { ll sum=0; FOR(j,i) sum+=G[j]*(G[j]+1)/2; while(G[j]*(G[j]+1)/2<=sum) G[j]++; } int mask; map<int,string> cand; FOR(mask,1<<12) { string A,B; FOR(i,12) { if(mask&(1<<i)) { B+="("; FOR(j,G[i+1]) A+="()"; } else { B+=")"; FOR(j,G[i+1]) A+="))"; } A+=")"; } int sum=0; FOR(x,A.size()) { int cur=0; for(y=0;x+y<A.size();y++) { if(A[x+y]=='(') cur++; else cur--; if(cur==0) sum++; if(cur<0) break; } } cand[sum]=B; } assert(cand.size()==1<<12); cin>>T; while(T--) { if(W.size()) { N=W.size(); } else { cin>>N; } S=string(N,'-'); vector<int> V; FOR(i,N) V.push_back(i); x=ask(V); if(x==0) { int L=0,R=N-1; S=string(N,'('); while(L+1<R) { int M=(L+R)/2; V={M,0}; if(ask(V)) { R=M; } else { L=M; } } FOR(i,L+1) S[i]=')'; } else { //Rなら確定 int L=0,R=N; while(L+1<R) { int M=(L+R)/2; V.clear(); FOR(i,M) V.push_back(i); if(ask(V)) R=M; else L=M; } x=R-2; S[x]='('; S[x+1]=')'; vector<int> Q; FOR(i,N) if(i!=x&&i!=x+1) Q.push_back(i); while(Q.size()%12) Q.push_back(Q[0]); FOR(y,Q.size()/12) { V.clear(); FOR(i,12) { FOR(j,G[i+1]) { V.push_back(Q[y*12+i]); V.push_back(x+1); } V.push_back(x+1); } r=ask(V); assert(cand.count(r)); string B=cand[r]; FOR(i,12) S[Q[y*12+i]]=B[i]; } } cout<<"! "<<S<<endl; } }
まとめ
本番なんとかC2まで解いたけど、この解法は全く思い浮かばなかった。