Mister雑記

競プロやります。

ARC095-E 「Symmetric Grid」 (700)

atcoder.jp

問題

 H \times Wのアルファベットからなるグリッドが与えられる。

この行と列を自由に入れ替えることで、点対称にできるか判定せよ。

制約

  •  1 \leq H, W \leq 12

考察

脳死 O(HW \times H! W!)をやりたくなるが、当然それは許されない。

そこで行の並び方だけ全列挙することにする。すると、「互いに逆の並びになっている列のペアで両端から埋めていく」という貪欲によって、列の並び方を全列挙することなく可能性判定ができる。

ただし Wが奇数の場合は注意が必要。このとき真ん中の列に来るものは他とペアになっている必要はないが、代わりに自分自身とペアになる、すなわち回文になっている必要がある。

これで O(HW^2 H!)に落ちるが、まだ際どい。そこで行の並べ方を枝刈りする。点対称なグリッドにおいて、その対称な位置にある行を交換してもこれは点対称である。よって、両端から「上の行の方が小さくなるように」行番号を2つずつ決めていけば、それで可能性を全列挙できたことになる。

これで O(HW^2 H!!)に落ち、 12!! = 12 \cdot 10 \cdot \cdots \cdot 2 = 46080なので割と際どいが間に合う。


以上の解法はEditorialそのままだが、難しいのは実装の方である。まず「両端から行番号を決めていく」というのが、いざ実装しようとすると結構面倒なことが分かる。そして何よりも「 H, Wが奇数」のケースが本当に面倒くさい。

通すまでに相当な数のバグを踏んだので、以下の実装例に自分が踏んだバグを一通り書いておく。

実装例

atcoder.jp

以下では無名構造体内部で探索するような実装をしているが、ただ「グローバル変数を増やしたくない」というだけの理由なので、気にならない人は普通にいくつか関数を宣言すればいいと思われる。

// 各関数は上から下に流れるようになっている
// ! で始まるコメントは自分が踏んだバグ
struct {
    Int h, w;
    Vector<Int> col;
    Vector<String> s, t;
    // sは入力 tは行を並び替えた後、転置したもの
    Bool possible;

    void operator()() {
        possible = false;
        std::cin >> h >> w;

        s.resize(h), t.resize(w);
        for (auto& x : s) std::cin >> x;
        for (auto& y : t) y.resize(h);  // ! tのresizeし忘れ

        col.resize(h);
        enumcol_center();
    }

    // 真ん中の行の列挙 
    // ! これを後回しにして、中心の全列挙をミスる
    void enumcol_center() {
        if (h % 2 == 0) {
            enumcol(0, 0);
        } else {
            for (Int x = 0; x < h; ++x) {
                col[h / 2] = x;
                enumcol(1 << x, 0);
            }
        }
    }

    // bは固定済みの行 iはいくつのペアを固定したか
    void enumcol(Int b, Int i) {
        Int x;
        for (x = 0; x < h; ++x) {
            if (!((b >> x) & 1)) break;
        }
        if (x == h) {
            align();
            return;  // ! ここでreturnしないとhを固定し始める
        }

        for (Int y = x + 1; y < h; ++y) {
            if (!((b >> y) & 1)) {
                col[i] = x;
                col[h - i - 1] = y;
                enumcol(b | (1 << x) | (1 << y), i + 1);
            }
        }
    }

    // colに従ってtを埋める
    void align() {
        for (Int y = 0; y < w; ++y) {
            for (Int x = 0; x < h; ++x) {
                t[y][x] = s[col[x]][y];
            }
        }
        check_center();
    }

    // 真ん中の行の列挙 
    // ! enumcol_center()と同じく
    void check_center() {
        if (w % 2 == 0) {
            check(0);
        } else {
            for (Int x = 0; x < w; ++x) {
                // 回文判定
                String z = t[x];
                std::reverse(z.begin(), z.end());
                if (z == t[x]) check(1 << x);
            }
        }
    }

    // 両端から、互いに逆なペアを決めていく
    // bは決定済みの行番号
    void check(Int b) {
        Int x;
        for (x = 0; x < w; ++x) {
            if (!((b >> x) & 1)) break;
        }

        if (x == w) {
            possible = true;
            return;  // ! ここで枝刈りしないと、全文字が同じケースで非常に時間がかかる
                     //   なんならYESを出力してexit()を呼んでもいい
        }

        String z = t[x];
        std::reverse(z.begin(), z.end());

        for (Int y = x + 1; y < w; ++y) {
            if (!((b >> y) & 1)) {
                if (t[y] == z) {
                    check(b | (1 << x) | (1 << y));
                    return;
                }
            }
        }
    }
} solve;

int main() {
    solve();
    std::cout << (solve.possible ? "YES" : "NO") << std::endl;
    return 0;
}

ちなみに、行列挙を「next_permutation()で枝刈りする」として手を抜くとTLEになる。