【AtCoder】ABC347 F - Non-overlapping Squares

問題

解法

適当に の領域を3つの長方形に区切り、さらにそれぞれの長方形から の正方形を取り出すと考えて良い。

その場合、3つの長方形の区切り方は以下の6つのいずれかになる。

|--------|     |--------|
|        |     |  |  |  |
|--------|     |  |  |  |
|        |     |  |  |  |
|--------|     |  |  |  |
|        |     |  |  |  |
|--------|     |--------|

|--------|     |--------|
|        |     |  |     |
|--------|     |  |     |
|    |   |     |  |-----|
|    |   |     |  |     |
|    |   |     |  |     |
|--------|     |--------|

|--------|     |--------|
|    |   |     |     |  |
|    |   |     |     |  |
|    |   |     |-----|  |
|--------|     |     |  |
|        |     |     |  |
|--------|     |--------|

この長方形の区切り方を全探索する。なお、上記の図の左側にある3つの切り方を試した後、90度回転してもう一度同様の処理を行うことで実装をやや楽にできる。

各長方形の中でマス目の総和が最大の正方形を取り出すときには、あらかじめ2次元累積和ですべての の正方形に対するマス目の総和を求めておき、その値を2次元セグメント木に乗せることで、2次元領域に対するRMQに帰着すれば良い。

#include "my_template.hpp"
#include "data_structure/cumulative_sum_2d.hpp"
#include "data_structure/segment_tree_2d.hpp"
#include "algebra/monoid_s/monoid_max.hpp"
using namespace std;

void solve() {
    INT(N, M);
    VV(i64, A, N, N);
    i64 ans = 0;
    REP(_, 2) {
        CumulativeSum2D<i64> cum(A);
        vector B(N - M + 1, vector<i64>(N - M + 1));
        REP(i, N - M + 1) REP(j, N - M + 1) B[i][j] = cum.sum(i, j, i + M, j + M);
        SegmentTree2D<MonoidMax<i64>> seg(B);
        // [       ]
        // x-------
        // [  ]y[  ]
        REP(x, M, N + 1 - M) {
            i64 v1 = seg.prod(0, 0, x - M + 1, N - M + 1);
            REP(y, M, N + 1 - M) {
                i64 v2 = seg.prod(x, 0, N - M + 1, y - M + 1);
                i64 v3 = seg.prod(x, y, N - M + 1, N - M + 1);
                chmax(ans, v1 + v2 + v3);
            }
        }
        // [  ]y[  ]
        // x-------
        // [       ]
        REP(x, M, N + 1 - M) {
            i64 v1 = seg.prod(x, 0, N - M + 1, N - M + 1);
            REP(y, M, N + 1 - M) {
                i64 v2 = seg.prod(0, 0, x - M + 1, y - M + 1);
                i64 v3 = seg.prod(0, y, x - M + 1, N - M + 1);
                chmax(ans, v1 + v2 + v3);
            }
        }
        // [      ]
        // x------
        // [      ]
        // y------
        // [      ]
        REP(x, M, N + 1 - M) {
            i64 v1 = seg.prod(0, 0, x - M + 1, N - M + 1);
            REP(y, x + M, N + 1 - M) {
                i64 v2 = seg.prod(x, 0, y - M + 1, N - M + 1);
                i64 v3 = seg.prod(y, 0, N - M + 1, N - M + 1);
                chmax(ans, v1 + v2 + v3);
            }
        }
        // rotate
        rot(A);
    }
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}

感想

Twitterを見ていたら「品目典型」と名付けられていて良いセンスだなと感心した。 類題として ABC062 C - Chocolate Bar が挙げられていたが、 1つの長方形を3つの長方形に分割する問題であり、今回のような3つの正方形を取る問題でも長方形から取り出すと考えることでこのテクニックを応用できるというのが勉強になった。