マス目のカット [第四回 アルゴリズム実技検定 H]

https://atcoder.jp/contests/past202010-open/tasks/past202010_h

前提知識

• 二次元累積和

解説

https://atcoder.jp/contests/past202010-open/submissions/21472353

根性実装する問題。
制約が小さいので、前提知識として挙げている二次元累積和を使わなくても解けそう。
（試してないので、ちゃんと計算量解析して）

nの値としてありうる値の最大値

制約が小さいのでnを大きい順から試していって切り出すことが出来たらそれを答えて、プログラム終了すればいい。
nの最大値を考えてみると正方形を切り抜く必要があるのでmin(W,H)となる。
n=1は絶対大丈夫なのでmin(W,H)から始めて1まで検査すればいい。

実際ここは単調性があるので二分探索を用いるとより高速化できる。
check(n) := 条件下において、サイズnの正方形を切り出せるか

check関数の実装

マス目上で抜き出せるすべての正方形とその正方形内部をどの数dに合わせるかを全列挙して、操作回数がK以下のものを探す。
どの数dに合わせるかも全列挙する所がミソで、これが決まることで正方形内部にdが何個あるかが分かれば、
全体の個数からその個数を引くことで、必要な回数が分かる。
これがK以下であれば、その正方形をすべてdにすることができる。
このような長方形区間にある要素が何個あるかを高速に数え上げるには二次元累積和を使うのがいい。
二次元累積和は単に数を足し合わせるだけなので、0～9それぞれに二次元累積和を作って個数を取ってこれるようにしよう。

ここまで言っていることが分かれば、全てをまとめることはそれほど難しくない。

int H, W, K;
string S[30];
Ruisekiwa2D r2d[10];
//---------------------------------------------------------------------------------------------------
bool check(int len) {
    rep(y, 0, H - len + 1) rep(x, 0, W - len + 1) rep(d, 0, 10) {
        int ng = len * len - r2d[d].get(x, x + len - 1, y, y + len - 1);
        if (ng <= K) return true;
    }
    return false;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> K;
    rep(y, 0, H) cin >> S[y];
    rep(i, 0, 10) r2d[i].init(W, H);
    rep(y, 0, H) rep(x, 0, W) r2d[S[y][x] - '0'].add(x, y, 1);
    rep(i, 0, 10) r2d[i].build();

    rrep(n, min(H, W), 1) if (check(n)) {
        cout << n << endl;
        return;
    }
}