問題概要

市松模様に塗られた $H \times W$ のマス目があって、各マスには整数値が書かれている。以下の条件を満たす長方形領域の面積の最大値を求めよ。

その長方形領域に含まれる、黒いマスの数値の総和と、白いマスの数値の総和が等しい

制約

$1 \le H, W \le 100$

考えたこと

まさに二次元累積和の練習問題！！！

黒いマスの数値はそのまま
白いマスの数値は -1 倍

というふうにしておくと、以下の条件に言い換えられる。

「長方形領域であって、それに含まれる数値の総和が 0」

二次元累積和を求めておくと、各長方形領域 ( $O((HW)^{2})$ 個ある) の数値の総和が $O(1)$ で求められるので、全体として $O((HW)^{2})$ の計算量で解ける。二次元累積和については以下の記事に。

qiita.com

コード

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

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<long long>> A(H, vector<long long>(W));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> A[i][j];
            if ((i+j) % 2 == 1) A[i][j] *= -1;
        }
    }
    vector<vector<long long>> S(H+1, vector<long long>(W+1, 0));
    for (int i = 0; i <= H; ++i) {
        for (int j = 0; j <= W; ++j) {
            if (i > 0) S[i][j] += S[i-1][j];
            if (j > 0) S[i][j] += S[i][j-1];
            if (i > 0 && j > 0) S[i][j] -= S[i-1][j-1], S[i][j] += A[i-1][j-1];
        }
    }
    int res = 0;       
    for (int i = 0; i <= H; ++i) {
        for (int j = 0; j <= W; ++j) {
            for (int i2 = i+1; i2 <= H; ++i2) {
                for (int j2 = j+1; j2 <= W; ++j2) {
                    if (S[i2][j2] - S[i2][j] - S[i][j2] + S[i][j] == 0) {
                        res = max(res, (i2-i)*(j2-j));
                    }
                }
            }
        }
    }
    cout << res << endl;
}

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

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

AtCoder ARC 025 B - チョコレート (試験管水色)

問題概要

制約

考えたこと

コード