SRM639D1Med BoardFolding

実装がきらい

問題概要(原文)

$N \times M$ の行列が与えられる.鏡像関係になっているなら,水平,または垂直線で折り返せる.最終的な紙の形状は何通りあるか?

考察

行,列の折り返しは独立に考えてよい.よって,列についての折り返しだけ考える.また,複数行の文字列ではなく $1$ 行の文字列であるとしても一般性を失わない. 前計算で, $l$ 列目と $r$ 目が一致するかを調べよう.

すると,以下のような区間DPを埋めればよい. $dp(l,r) = $ $[l,r)$ のような形にすることが可能かどうか.

これは適当に遷移すると, $O(M^4)$ ぐらいかかって間に合わない. 長い方からだんだん短くしていけばよい. つまり $r-l = M$ から始めて, $r-l = 1$ になるように遷移を試す. そこから右向きに展開,左向きに展開するのを試す.

計算量は $O(N(N^{2} + M^{2}) + M(N^{2} + M^{2}))$ とかそんなの.

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class BoardFolding
{
    public int howMany(int n, int m, string[] compressedPaper)
    {
        var a = Enumerate(n, x => new int[m]);
        var b = Enumerate(m, x => new int[n]);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
            {
                var x = 0;
                var y = compressedPaper[i][j / 6];
                if (char.IsDigit(y))
                    x = compressedPaper[i][j / 6] - '0';
                else if (y == '#') x = 62;
                else if (y == '@') x = 63;
                else if (char.IsLower(y)) x = 10 + y - 'a';
                else x = 36 + y - 'A';

                x >>= (j % 6);
                x %= 2;
                a[i][j] = b[j][i] = x;
            }
        var p = f(a);
        var q = f(b);
        return p * q;
    }
    int f(int[][] a)
    {
        foreach (var x in a)
            Debug.WriteLine(x.AsJoinedString());
        var n = a.Length;
        var m = a[0].Length;
        var same = Enumerate(m, x => new bool[m]);
        for (int i = 0; i < m; i++)
            for (int j = i + 1; j < m; j++)
            {
                same[i][j] = true;
                for (int k = 0; k < n; k++)
                    same[i][j] &= a[k][i] == a[k][j];
            }
        var dp = Enumerate(m, x => new bool[m]);
        dp[0][m - 1] = true;
        var ret = 1;
        for (int len = m - 1; len >= 1; len--)
        {
            for (int l = 0; l < m; l++)
            {
                var r = l + len - 1;
                if (r >= m) continue;
                dp[l][r] = false;
                for (int x = l - 1; x >= 0 && !dp[l][r]; x--)
                {
                    if (l - x > r - l + 1) break;
                    if (!same[x][l + (l - x - 1)]) break;
                    dp[l][r] |= dp[x][r];
                }
                for (int x = r + 1; x < m && !dp[l][r]; x++)
                {
                    if (x - r > r - l + 1) break;
                    if (!same[r - (x - r - 1)][x]) break;
                    dp[l][r] |= dp[l][x];
                }
                if (dp[l][r]) ret++;
            }
        }
        return ret;


    }
    static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
    static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }

}
static public class EnumerableEX
{
    static public string AsString(this IEnumerable<char> e) { return new string(e.ToArray()); }
    static public string AsJoinedString<T>(this IEnumerable<T> e, string s = " ") { return string.Join(s, e); }
}

コメント

  • 実装力がなさすぎる