TopCoder SRM 591 Div2 Medium ConvertibleStrings

この回もDiv2 MediumがDiv1とは違う問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12754

問題

2つの文字列A・Bが与えられる。
AおよびBからいくつか文字を取り除き、AからBに変換できる各文字の全単射関数が存在するようにしたい。
取り除く文字数を最小化せよ。

解法

登場する文字はA～Iの9文字だけ。
なので9!通り分の全単射関数を実際に作り、変換ルールに合わない文字の数を数えればよい。
以下ではnext_permutationを使ってみた。

class ConvertibleStrings {
	public:
	int leastRemovals(string A, string B) {
		string T="ABCDEFGHI";
	
		int mi=10000;
		do {
			int i,j=0;
			FOR(i,B.size()) j += B[i]!=T[A[i]-'A'];
			mi = min(mi,j);
		} while(next_permutation(T.begin(),T.end()));
		return mi;
		
	}
};

まとめ

next_permutation知らないとDFSとか使って書くことになって面倒だね。