不参加だったけど、Div1Easy 1ミスしたので結果的に正解か。
http://community.topcoder.com/stat?c=problem_statement&pm=14074
問題
アルファベット大文字からなる文字列に対する換字暗号を考える。
換字のルールは不明だが、文字列Aを変換するとBになることが分かっている。
ある文字列Xを変換したところYになった。
Yがわかっているとき、Xを一意に求められるか。求められるならXを求めよ。
解法
暗号化したものを戻すと考えると難しいが、B→Aと同じルールでY→Xを変換すると考えると簡単である。
文字列のAとBから換字のルールを求め、Yに適用してやればよい。
1点注意点として、AとBがそれぞれ25種類のアルファベットを含むとき、残る1種のアルファベットの換字ルールも特定できる。
class SubstitutionCipher { public: string decode(string a, string b, string y) { int to[26]; int i,x,used=0; FOR(i,26) to[i]=-1; FOR(i,a.size()) to[b[i]-'A']=a[i]-'A', used |= 1<<(a[i]-'A'); if(__builtin_popcount(used)==25) { FOR(i,26) if(to[i]==-1) { FOR(x,26) if((used&(1<<x))==0) to[i]=x; } } FORR(r,y) { if(to[r-'A']==-1) return ""; r=to[r-'A']+'A'; } return y; } }
まとめ
25種類の文字のケース、絶対コーナーケースになるのにあえてサンプルで教えているのは易しい。