kmjp's blog

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

Codeforces #1040 : Div1. C3. Interactive RBS (Hard Version)

コード結構長いな。
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まで解いたけど、この解法は全く思い浮かばなかった。