kmjp's blog

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

TopCoder SRM 672 Div2 Medium SubstitutionCipher

不参加だったけど、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種類の文字のケース、絶対コーナーケースになるのにあえてサンプルで教えているのは易しい。