TopCoder SRM 591: ConvertibleStrings

文字の種類は 'A'... 'I' の９種類しかない。
となると ('A'...'I') -> ('A'...'I') の割り当ての仕方は 9! になるため、全部試しても間に合う。それぞれの割り当てについて、割り当て通りではない (A[i], B[i]) を削除すればよい。

next_permution は C♯ にないため、自前で実装した。

public class ConvertibleStrings {
    static public void Swap<T>(ref T a, ref T b) {
        T t = a;
        a = b;
        b = t;
    }

    static public bool NextPermutation<T>(T[] array) where T : IComparable<T> {
        int n = array.Length;
        for (int i = n - 2; i >= 0; i--) {
            if (array[i].CompareTo(array[i + 1]) < 0) {
                var index = Array.FindLastIndex(array, v => array[i].CompareTo(v) < 0);
                Swap(ref array[i], ref array[index]);
                Array.Reverse(array, i + 1, n - (i + 1));
                return true;
            }
        }
        Array.Reverse(array);
        return false;
    }

    public int leastRemovals(string A, string B) {
        int n = A.Length;
        var s = "ABCDEFGHI".ToCharArray();
        int ans = int.MaxValue;
        do {
            int remove = 0;
            for (int i = 0; i < n; i++) {
                if (s[A[i] - 'A'] != B[i]) remove++;
            }
            ans = Math.Min(ans, remove);
        } while (NextPermutation(s));
        return ans;
    }
}