Codeforces #610 Div2 D. Enchanted Artifact

不参加だった回。
https://codeforces.com/contest/1282/problem/D

問題

a,bだけで構成される文字列Sを当てるinteractive問題である。
文字列を指定すると、Sとの編集距離が返るクエリがある。
このクエリを最大|S|+2回まで用いて、Sを当てよ。

解法

aだけで構成されたクエリと、bだけで構成されたクエリを1回ずつ投げるとa,bの数がわかる。
あとはbb....bbの間に、aの追加位置を1つずつ前から試していこう。
失敗するのはbの登場回数だけなので、aの登場回数分成功するまでにかかるクエリ回数は高々|S|+2となる。

int ask(string S) {
	int ret;
	cout<<S<<endl;
	cin>>ret;
	if(ret==0) exit(0);
	return ret;
}

string create(vector<int> V) {
	int i,j;
	string S;
	FOR(i,V.size()) {
		if(i) S+="b";
		FOR(j,V[i]) S+="a";
	}
	return S;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int A=300-ask(string(300,'a'));
	int B=300-ask(string(300,'b'));
	
	if(A==0) ask(string(B,'b'));
	if(B==0) ask(string(A,'a'));
	
	vector<int> V(B+1);
	
	
	int fixed=B;
	int nex=0;
	FOR(i,A) {
		fixed++;
		while(1) {
			V[nex]++;
			x=ask(create(V));
			if(x==A+B-fixed) break;
			V[nex]--;
			nex++;
		}
		
	}
}

まとめ

実際編集距離を求めるコードを書かなくていいのは楽。