https://atcoder.jp/contests/abc264/tasks/abc264_c

前提知識

bit全探索

解法

パっと見た感じ難しい問題に見えると思う。
この問題で注目すべき部分は制約である。
盤面のサイズがとても小さく、最大でも10。
制約が小さいということは、少し無茶な解法でも通るのではという発想になる。
（あとC問題ということもちょっと考える）

全探索

解法の基本は全探索なので、全探索を考えてみよう。
例えば2番目の行と3番目の行と3番目の列を消そうと考えたときに、

2番目の行 -> 3番目の行 -> 3番目の列という順番で消しても、
3番目の行 -> 2番目の行 -> 3番目の列という順番で消しても、
3番目の列 -> 3番目の行 -> 2番目の行という順番で消しても、
最終的な形としては全く同じになる。

つまり、問題文としては操作を繰り返すということになっているが、選択肢としては各行、各列について消すか消さないかということになる。
消すか消さないかの2択を行と列の最大20か所について確認するので全部で2²⁰通りあることになる。
これは1048576通りなので、だいたい10⁶通りで間に合う個数といえる。
（10⁶とか10⁷くらいが間に合うかどうかの境目になってくる）

どうやって全探索するか

こういった、やる/やらないの全探索はbit全探索という方法で行うのがオススメ。
やり方は専門の記事を参照する方が双方効率がいいのでgoogleで「bit全探索」と検索して学ぶとよい。

ビット全探索で各行、各列について残す行と列を決めたら、それ以外は消してから行列Bと比較する必要がある。
この実装部分もちょっと苦戦するかもしれない。
自分はbit全探索部分含めて以下のように実装した。

    rep(usedRow, 0, 1 << H1) rep(usedColumn, 0, 1 << W1) {   // bit全探索部分（残す部分を1として全探索している）
        // 残す部分の長さが行列Bと一緒かどうかチェック
        int H3 = 0;
        rep(y, 0, H1) if (usedRow & (1 << y)) H3++;
        int W3 = 0;
        rep(x, 0, W1) if (usedColumn & (1 << x)) W3++;
        if (H3 != H2 || W3 != W2) continue;

        // 行列Aから行と列を消して行列Cを作るとする
        int cy = 0;
        rep(y, 0, H1) if (usedRow & (1 << y)) {
            int cx = 0;
            rep(x, 0, W1) if (usedColumn & (1 << x)) {
                C[cy][cx] = A[y][x];
                cx++; // ここが大事。Aの値を入れたときにcのx座標を一つ右にずらす
            }
            cy++; // ここも同様。行列Cの行が1行処理されたらy座標を1つ下にずらす
        }

        // 行列Cができたら縦横の長さ同じはずなので、適当にループで行列Bと等しいかチェック
        bool ok = true;
        rep(x, 0, W2) rep(y, 0, H2) if (B[y][x] != C[y][x]) ok = false;
        if (ok) return YES;
    }

インラインで解説を入れておいた。
行列Cを作る方法としては、行/列の削除関数を作って、1つずつ消していくやり方などがあると思う。
今回の解法はO(2^H+W HW)なので、意外と計算量に余裕がないかもしれないけど。

今回はO(2^H+W HW)で解いたが、本番はO(WH 2^H)で解いたのでそちらも時間があれば見てみてほしい。
https://atcoder.jp/contests/abc264/submissions/33999413
行だけbit全探索で全探索して、列の方は貪欲法で解いている。

https://atcoder.jp/contests/abc264/submissions/34023787

int H1, W1;
int A[10][10];

int H2, W2;
int B[10][10];

int C[10][10];

#define YES "Yes"
#define NO "No"

string solve() {
    rep(usedRow, 0, 1 << H1) rep(usedColumn, 0, 1 << W1) {
        int H3 = 0;
        rep(y, 0, H1) if (usedRow & (1 << y)) H3++;
        int W3 = 0;
        rep(x, 0, W1) if (usedColumn & (1 << x)) W3++;

        if (H3 != H2 || W3 != W2) continue;

        int cy = 0;
        rep(y, 0, H1) if (usedRow & (1 << y)) {
            int cx = 0;
            rep(x, 0, W1) if (usedColumn & (1 << x)) {
                C[cy][cx] = A[y][x];
                cx++;
            }
            cy++;
        }

        bool ok = true;
        rep(x, 0, W2) rep(y, 0, H2) if (B[y][x] != C[y][x]) ok = false;
        if (ok) return YES;
    }

    return NO;
}

void _main() {
    cin >> H1 >> W1;
    rep(y, 0, H1) rep(x, 0, W1) cin >> A[y][x];
    cin >> H2 >> W2;
    rep(y, 0, H2) rep(x, 0, W2) cin >> B[y][x];

    cout << solve() << endl;
}

はまやんはまやんはまやん

hamayanhamayan's blog

Matrix Reducing [freee プログラミングコンテスト2022（AtCoder Beginner Contest 264） C]

前提知識

解法

全探索

どうやって全探索するか