TopCoder SRM600: PalindromeMatrix

回文になる行の集合を全通り試す。

回文になる行の箇所が固定されると、(0列とW-1列), (1列とW-2列）... のペアそれぞれについて独立に処理できるため、あとは動的計画法で処理できる。

本番だと、i列と(W-1-i)列のペアについて、「i列が回文である / でない」×「(W-1-i列)が回文である / でない」の４通りについて、PalindromeMatrixDiv2 と同様に連結情報を求めて処理させようとしたけれど、実装が重くて間に合わなかった。

以下の解では、「i列が回文である」と「W-1-i列が回文である」を状態にした動的計画法を使って計算している。

public class PalindromeMatrix {
    static public void Swap<T>(ref T a, ref T b) { T t = a; a = b; b = t; }
    static public void UpdateMin<T>(ref T x, T newValue) where T : IComparable<T> { if (x.CompareTo(newValue) > 0) x = newValue; }
    static public void Fill<T>(T[] array, T value) { for (int i = 0; i < array.Length; i++) array[i] = value; }

    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;
    }
    int R, C;
    string[] A;
    int?[,] memo;
    bool[] perm;

    int dfs(int firstPos, int lastPos, int columnCount) {
        if (columnCount <= 0) columnCount = 0;
        if (firstPos >= lastPos) {
            if (columnCount == 0) return 0;
            return 1 << 28;
        }
        if (!memo[firstPos, columnCount].HasValue) {
            int val = 1 << 28;

            var dp = new int[4];
            var next = new int[4];

            for (int r1 = 0, r2 = R - 1; r1 < r2; r1++, r2--) {
                Fill(next, 1 << 28);
                // r11 ... r12
                // r21 ... r22
                for (int i = 0; i < 4; i++) {
                    for (int k = 0; k < 16; k++) {
                        var r11 = ((k & 1) != 0 ? 1 : 0) + '0';
                        var r12 = ((k & 2) != 0 ? 1 : 0) + '0';
                        var r21 = ((k & 4) != 0 ? 1 : 0) + '0';
                        var r22 = ((k & 8) != 0 ? 1 : 0) + '0';

                        if (r11 != r21 && (i & 1) != 0) continue;
                        if (r12 != r22 && (i & 2) != 0) continue;
                        if (perm[r1] && r11 != r12) continue;
                        if (perm[r2] && r21 != r22) continue;

                        int change = 0;
                        if (r11 != A[r1][firstPos]) change++;
                        if (r12 != A[r1][lastPos]) change++;
                        if (r21 != A[r2][firstPos]) change++;
                        if (r22 != A[r2][lastPos]) change++;

                        UpdateMin(ref next[i], change);
                    }
                    dp[i] += next[i];
                    if (dp[i] >= (1 << 28)) dp[i] = 1 << 28;
                }
            }

            for (int i = 0; i < 4; i++) {
                int remainCount = columnCount;
                if ((i & 1) != 0) remainCount--;
                if ((i & 2) != 0) remainCount--;
                UpdateMin(ref val, dp[i] + dfs(firstPos + 1, lastPos - 1, remainCount));
            }

            memo[firstPos, columnCount] = val;
        }
        return memo[firstPos, columnCount].Value;
    }

    public int minChange(string[] A, int rowCount, int columnCount) {
        this.A = A;
        this.R = A.Length;
        this.C = A[0].Length;

        this.perm = new bool[R];
        for (int i = 0; i < rowCount; i++) {
            perm[i] = true;
        }
        Array.Sort(perm);
        int ans = int.MaxValue;
        do {
            memo = new int?[20, 20];
            ans = Math.Min(ans, dfs(0, C - 1, columnCount));
        } while (NextPermutation(perm));
        return ans;
    }
}