AOJ 1059 Mysterious Onslaught

解けるまで

2^25のdp(char dp[1 << 25])で通そうとがんばっていた
枝狩り + unordered_mapなどゴリ押ししようとするがMLE取れず
2^25以上の配列を確保して通っている人がいるのに謎

実は工夫すれば2^25の状態のdpで通せる
求めたい最大の答えは16未満なので、1つの状態に対して4bitあれば十分
charに2つの状態を詰めます -> char dp[1 << 24]で2^25の状態数持てる

2^25の状態のdpは想定解法ではないみたい

解法

4行 * 5列の状態を求めておく。そうすると、n <= 4に対してはO(1)

n = 5のときは5行目を含むような長方形を全探索する
探索の際に長方形の左下もしくは右下が一致するようなケースは考えなくて良い。一致するような場合、領域が重ならない2つの長方形にできるから。
探索はdfsでする
長方形を1つ取るごとに、左下と右下それぞれの候補が1つ減るので、5つ以上の長方形を取る必要はない
探索される状態はdfsの各深さで、長方形の高さ * 左下 * 右下なので、全体で以下

ソースコード

int xor_mask[5][5][5][5];
int cost[1 << 20]; /// 4 rows * 5 cols
void pre()
{
    // myon mask
    for (int y1 = 0; y1 < 5; ++y1)
    {
        for (int x1 = 0; x1 < 5; ++x1)
        {
            for (int y2 = y1; y2 < 5; ++y2)
            {
                for (int x2 = x1; x2 < 5; ++x2)
                {
                    int mask = 0;
                    for (int y = y1; y <= y2; ++y)
                        for (int x = x1; x <= x2; ++x)
                            mask |= 1 << (5 * y + x);
                    xor_mask[y1][x1][y2][x2] = mask;
                }
            }
        }
    }

    // bfs
    CL(cost, -1);
    queue<int> q;
    cost[0] = 0;
    q.push(0);
    while (!q.empty())
    {
        int cur = q.front();
        int ncost = cost[cur] + 1;
        q.pop();

        for (int y1 = 0; y1 < 4; ++y1)
        {
            for (int x1 = 0; x1 < 5; ++x1)
            {
                for (int y2 = y1; y2 < 4; ++y2)
                {
                    for (int x2 = x1; x2 < 5; ++x2)
                    {
                        int next = cur ^ xor_mask[y1][x1][y2][x2];
                        if (cost[next] == -1)
                        {
                            cost[next] = ncost;
                            q.push(next);
                        }
                    }
                }
            }
        }
    }
}

int res;
bool used_left[5], used_right[5];
void dfs(int e, int c, int depth)
{
    if (depth >= 5 || c >= res /* この枝狩りは申し訳程度の高速化 */)
        return;
    else if (e < (1 << 20))
    {
        min_swap(res, c + cost[e]);
        return;
    }

    for (int left = 0; left < 5; ++left)
    {
        if (!used_left[left])
        {
            used_left[left] = true;

            for (int right = left; right < 5; ++right)
            {
                if (!used_right[right])
                {
                    used_right[right] = true;

                    for (int y = 0; y < 5; ++y)
                        dfs(e ^ xor_mask[y][left][4][right], c + 1, depth + 1);

                    used_right[right] = false;
                }
            }

            used_left[left] = false;
        }
    }
}
int main()
{
    fast_io();
    pre();

    string myon[33];
    myon[0] = "";
    for (int i = 0; i < 30; ++i)
        myon[i + 1] = myon[i] + "myon";

    int n;
    while (cin >> n, n)
    {
        int e = 0;
        for (int y = 0; y < n; ++y)
        {
            for (int x = 0; x < n; ++x)
            {
                int t;
                cin >> t;
                e |= t << (y * 5 + x);
            }
        }

        // shift upward if no enemies in 1st row
        const int first_row = ((1 << 5) - 1);
        while (!(e & first_row) && e)
            e >>= 5;

        res = 25;
        dfs(e, 0, 0);
        cout << myon[res] << endl;
    }
}