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); }
}
コメント
- 実装力がなさすぎる
