読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

ARC025 B - チョコレート

競プロ 累積和

バレンタインということで(?)

問題

arc025.contest.atcoder.jp

縦Hマス、横Wマスのチョコレートがある。各マスはブラックチョコかホワイトチョコであり、これらは市松模様に並んでいる。

各マス (i, j)について、チョコの濃度 C_{i, j}が与えられている。このチョコレートから、ブラックチョコとホワイトチョコの濃度が等しくなるように長方形領域を切り取るとき、この長方形領域の最大のマス数を求めよ。

制約

 1 \leq H \leq 100

 1 \leq W \leq 100

 0 \leq C_{i, j} \leq 99

解法

各長方形領域の内部に含まれるブラックチョコとホワイトチョコの和が必要になります。ということで2次元累積和。 ただし今回はブラックチョコとホワイトチョコの和を別々に求めたいので、2パターンの累積和を取ります。

あるマスがブラックかホワイトかは、添え字の和 i + jが奇数か偶数かを使えばOK。

以下の解答では長方形の左上を (i + 1, j + 1), 右下を (k, l)で表しています。(こうすると領域内の和を出すときに「どこで-1するんだっけ?」とか考えなくてよい)

ちなみにPythonだとTLEしたのでC++です(怒)

const int MAX_H = 110;
const int MAX_W = 110;
int H, W;
int C[MAX_H][MAX_W];
int b[MAX_H][MAX_W];
int w[MAX_H][MAX_W];
 
void input() {
    scanf("%d%d", &H, &W);
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            scanf("%d", &C[i][j]);
        }
    }
}
 
int func(int i, int j, int k, int l) {
    int nb = b[k][l] - b[k][j] - b[i][l] + b[i][j];
    int nw = w[k][l] - w[k][j] - w[i][l] + w[i][j];
    if (nb == nw)
        return (k-i) * (l-j);
    return 0;
}
 
void solve() {
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if ( (i + j) % 2 != 0 ) {
                w[i][j] += C[i][j] + w[i][j-1];
                b[i][j] += b[i][j-1];
            } else {
                w[i][j] += w[i][j-1];
                b[i][j] += C[i][j] + b[i][j-1];
            }
        }
    }
 
    for (int j = 1; j <= W; j++) {
        for (int i = 1; i <= H; i++) {
            w[i][j] += w[i-1][j];
            b[i][j] += b[i-1][j];
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            for (int k = i; k <= H; k++) {
                for (int l = j; l <= W; l++) {
                    ans = max(ans, func(i, j, k, l));
                }
            }
        }
    }
 
    printf("%d\n", ans);
}
 
int main() {
    input();
    solve();
    return 0;
}

B問題もちょこちょこ解けるのが増えてきて嬉しい。