Codeforces #612 Div1 C2. Madhouse

EasyとHardの差異が独特な問題。
https://codeforces.com/contest/1286/problem/C2

問題

文字列Sの文字列長Nが与えられるので、Sを求めるinteractive問題である。
実行可能なクエリとして、区間[L,R]を指定すると、S[L,R]のsubstringをそれぞれシャッフルしたものを順不同で返す。
このクエリを最大3回まで使用し、かつ返るsubstring数がfloor(0.777(N+1)^2)以下となるようにして、Sを求めよ。

解法

substringはシャッフルして返るため、情報としては文字の登場頻度しか使えない。

Easyはsubstring数の上限が大きいので余裕がある。
S[0...(N-1)]とS[1...(N-1)]のクエリを投てその差を取れば、S[0]を含むsubstringを列挙できる。

Hardはsubstring数の上限が小さい。
そこで、S[0...(N-1)]とS[0...N/2]とS[1...N/2]の結果を取ろう。
後ろ2つの結果を用いるとEasyと同じ要領でSの前半分は特定できる。

後ろ半分について、各位置の文字が先頭のクエリの結果において何文字のsubstringに何回出てくるかを考え、条件を満たすものを選んでいこう。

int N;
string H;
int q=0;

vector<string> ask(int L,int R) {
	vector<string> V;
	cout<<"? "<<L<<" "<<R<<endl;
	int len=R-L+1;
	int i;
	if(H.size()) {
		for(int l=L;l<=R;l++) for(int r=l;r<=R;r++) V.push_back(H.substr(l-1,r-l+1));
		FORR(v,V) sort(ALL(v));
		random_shuffle(ALL(V));
	}
	else {
		FOR(i,len*(len+1)/2) {
			string S;
			cin>>S;
			sort(ALL(S));
			V.push_back(S);
		}
	}
	q+=V.size();
	return V;
}
string ans(string S) {
	cout<<"! "<<S<<endl;
	exit(0);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	if(H.size()) {
		N=H.size();
	}
	else {
		cin>>N;
	}
	
	if(N<=3) {
		string S;
		FOR(i,N) S+=ask(i+1,i+1)[0];
		ans(S);
		return;
	}
	
	auto A=ask(1,(N+1)/2);
	auto B=ask(2,(N+1)/2);
	auto D=ask(1,N);
	int T[101][26]={};
	FORR(a,A) FORR(c,a) T[a.size()][c-'a']++;
	FORR(a,B) FORR(c,a) T[a.size()][c-'a']--;
	string R(N,'.');
	for(i=1;i<=(N+1)/2;i++) {
		FOR(j,26) if(T[i][j]>T[i-1][j]) R[i-1]=j+'a';
	}
	int C[101][26]={};
	FORR(d,D) FORR(c,d) C[d.size()][c-'a']++;
	for(i=N/2;i>=0;i--) {
		FOR(j,26) {
			int c=C[i+1][j]-C[i][j];
			for(x=i+1;x<=N-i;x++) if(R[x-1]==j+'a') c--;
			if(c) R[N-i-1]=j+'a';
		}
	}
	ans(R);
	
	
}

まとめ

Easyはさっくり解けたんだけどね。