JOI '22 二次予選 C-国土分割

JOI 2021/2022 二次予選 C-国土分割(難易度7)

バグらせずに実装できたの嬉しいな

問題概要

の配列 が与えられるので区間内の数の総和が等しくなるような分割方法の総数を求めてください。

制約

考えたこと

とが小さいのでくらいまで通るだろうと考えました。
また、上から番目のすぐ下、左から番目のすぐ右でまず分割し、上から番目以降、左から番目以降の区間を分割すると考えると、残りの分割方法は一意に定まります。

なので、全てのの組に対し、それぞれの分割方法を求める　→　それぞれの区間の数の総和が等しければで答えがもとめられます。
この方法は

• の組は通り。
• それぞれの分割方法において、区間の数の総和が等しいかどうかの判定は二次元累積和を使ってでできる。

したがって全体としてで間に合います。

実装

めちゃくちゃバグらせそうな部分が多くて怖かったです。
あと結構実装がめんどかった。
(マクロとかは気合いで読んでください)
この解法だと線を一本も引かない(分割をしない)場合も数えてしまっているので最後にをしています

void Main () {
    ll H, W;
    cin >> H >> W;
    vvll A(H, vll(W));
    rep(i, H) vector_cin(A[i]);
    vvll B(A);
    rep(i, H) reps(j, W - 1) B[i][j] += B[i][j - 1];
    rep(j, W) reps(i, H - 1) B[i][j] += B[i - 1][j];
    ll ans = 0;
    rep(h, H) {
        rep(w, W) {
            ll S = B[h][w];
            vll H_del = {h}, W_del = {w};
            ll pre_i = h, pre_j = w;
            for (int i = h + 1; i < H; i++) {
                ll T = B[i][w] - B[pre_i][w];
                if (T == S) {
                    H_del.pb(i);
                    pre_i = i;
                }
            }
            for (int j = w + 1; j < W; j++) {
                ll T = B[h][j] - B[h][pre_j];
                if (T == S) {
                    W_del.pb(j);
                    pre_j = j;
                }
            }
            bool ok = true;
            if (H_del.back() != H - 1) H_del.pb(H - 1);
            if (W_del.back() != W - 1) W_del.pb(W - 1);
            rep(i, H_del.size()) {
                rep(j, W_del.size()) {
                    ll T = -1;
                    if (i == 0 && j == 0) T = B[H_del[i]][W_del[j]];
                    if (i == 0 && j > 0) T = B[H_del[i]][W_del[j]] - B[H_del[i]][W_del[j - 1]];
                    if (i > 0 && j == 0) T = B[H_del[i]][W_del[j]] - B[H_del[i - 1]][W_del[j]];
                    if (i > 0 && j > 0) T = B[H_del[i]][W_del[j]] - B[H_del[i - 1]][W_del[j]] - B[H_del[i]][W_del[j - 1]] + B[H_del[i - 1]][W_del[j - 1]];
                    if (S != T) {
                        ok = false;
                        break;
                    }
                }
            }
            if (ok) ans++;
        }
    } 
    cout << --ans << endl;
}

ACコード

atcoder.jp