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とはいえ簡単な方の問題だと思うけどな。