けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 春合宿 2007 day1-3 Mall (難易度 5)

JOI JOI春合宿 JOI難易度5 AtCoder 累積和 二次元累積和 【問題集】累積和 【問題集】二次元累積和 累積和テク:区間の総和を累積和で高速に求める

二次元累積和！！

問題概要

H \times W のグリッドが与えられる。各マスには整数値 A_{i, j} が描かれている。整数値は -1 以上 100 以下である。

これらのグリッド中の A \times B の長方形領域であって、その内部に -1 を含まないものを考える。そのような長方形領域に含まれる値の総和の最小値を求めよ。

ただし、内部に -1 を含まない長方形領域が存在することは保証される。

制約

  • 1 \le A \le H \le 1000
  • 1 \le B \le W \le 1000

考えたこと

整数値 -1 を INF に置き換えておけば、任意の長方形領域を考える問題に置き換えることができる。

このとき、 A の二次元累積和を求めておけば、各長方形領域の値の総和はそれぞれ O(1) で求めることができる。二次元累積和について、詳細は以下の記事より。

qiita.com

計算量は O(HW) となる。

コード

入力は H, W がいつもと逆に与えられるので、入力段階で補正して受け取っている。

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1LL<<40;
int main() {
    int H, W, A, B;
    cin >> H >> W >> A >> B;
    vector<vector<long long>> fi(H+1, vector<long long>(W+1, 0));
    for (int i = 1; i <= W; ++i) {
        for (int j = 1; j <= H; ++j) {
            cin >> fi[j][i];
            if (fi[j][i] == -1) fi[j][i] = INF;
        }
    }

    // 二次元累積和
    for (int i = 0; i <= H; ++i) for (int j = 1; j <= W; ++j) fi[i][j] += fi[i][j-1];
    for (int j = 0; j <= W; ++j) for (int i = 1; i <= H; ++i) fi[i][j] += fi[i-1][j];

    // 求める
    long long res = INF;
    for (int i = 0; i + A <= H; ++i) {
        for (int j = 0; j + B <= W; ++j) {
            res = min(res, fi[i+A][j+B] - fi[i+A][j] - fi[i][j+B] + fi[i][j]);
        }
    }
    cout << res << endl;
}