kmjp's blog

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

Codeforces ECR #060 : E. Decypher the String

1位でした。
https://codeforces.com/contest/1117/problem/E

問題

文字列をシャッフルする機械がある。
任意の文字列を入れると、シャッフル結果を返す。
シャッフルの仕方は毎回同一である。

この機械を3回まで使えるとき、最初の入力文字列のシャッフル結果を求めよ。

解法

入力は10000文字以下なので、26^3より小さい。
よって、n回目のクエリでは、i文字目にはiを26進数表記したものの下からn桁目を入れるようにすれば、3回でどの位置がどこに行くかすべて特定できる。

int N;
string S;
string T;

int hoge[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	
	FOR(i,3) {
		T.clear();
		FOR(j,N) {
			if(i==0) T.push_back('a'+(j%26));
			if(i==1) T.push_back('a'+(j/26%26));
			if(i==2) T.push_back('a'+(j/26/26%26));
		}
		cout<<("? "+T)<<endl;
		cin>>T;
		FOR(j,N) {
			x=(T[j]-'a')%26;
			if(i==0) hoge[j]+=x;
			if(i==1) hoge[j]+=26*x;
			if(i==2) hoge[j]+=26*26*x;
		}
	}
	
	FOR(i,N) T[hoge[i]]=S[i];
	cout<<"! "+T<<endl;
}

まとめ

本番解いてる人少ないけど、Div2とはいえ簡単な方の問題だと思うけどな。