ARC025 B - チョコレート

バレンタインということで（？）

問題

arc025.contest.atcoder.jp

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

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

制約

解法

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

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

以下の解答では長方形の左上を, 右下をで表しています。（こうすると領域内の和を出すときに「どこで-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問題もちょこちょこ解けるのが増えてきて嬉しい。