AtCoder Regular Contest 089 D: Checker

問題概要

日本語なので原文参照 → D - Checker

解説

公式解説 が詳しく書かれていますので、そちらもご覧ください。ここでは実装上楽な書き方を中心に書きたいと思います。

考慮すべき領域は以下のような形をしており、 箇所の累積和を求めれば良いです。これらの領域の位置は、領域 の右下を定めるとすべて定まります。黒の累積和・白の累積和をとって足して・・・と書いても出来ますが、今回は累積和の配列を つだけ使って実装してみましょう。

黒が置いてあるところはインクリメントし、白が置いてあるところはデクリメントすることを考えます。黒で塗りたい領域を決定したとき、黒は して白は しているため、決定した領域内に本当に黒が置いてあれば、条件を満たしているのでそのぶん加点されますし、白が置いてあれば、条件を満たしていないのでそのぶんペナルティとして減点される、というイメージになります。

このようにすると、白の要素の個数を覚えておくことで、 (累積和) + (白の要素の個数) とすれば、領域を決定した時に得られる値が分かります。

先ほど決定した領域の白黒を反転した状態における値の計算も簡単にできます。 (黒の個数) - (白の個数) と定義すると、盤面全体の累積和は と一致しています。白黒を反転しているため、 (累積和) とすることで、領域を反転させた際に得られる値が分かります。

ソースコード

#include <cstdio>
using namespace std;

int max(int a, int b) { return a < b ? b : a; }
int board[2010][2010];
int main() {
    int N, K; scanf("%d%d", &N, &K);

    int sum = 0, white = 0;
    for(int i=0; i<N; i++) {
        int x, y; char c; scanf(" %d%d %c", &x, &y, &c);
        x %= 2*K, y %= 2*K;
        if(c == 'B') board[x+1][y+1]++, sum++;
        if(c == 'W') board[x+1][y+1]--, sum--, white++;
    }

    for(int i=1; i<=2*K; i++) {
        for(int j=1; j<=2*K; j++) {
            board[i][j] += board[i][j-1];
        }
    }

    for(int j=1; j<=2*K; j++) {
        for(int i=1; i<=2*K; i++) {
            board[i][j] += board[i-1][j];
        }
    }

    int ma = -(1 << 25);
    for(int i=0; i<=K; i++) {
        for(int j=0; j<=K; j++) {
            int a = board[i][j];
            int b = board[i+K][j+K] - board[i+K][j] - board[i][j+K] + board[i][j];
            int c = board[2*K][j] - board[i+K][j];
            int d = board[i][2*K] - board[i][j+K];
            int e = board[2*K][2*K] - board[2*K][j+K] - board[i+K][2*K] + board[i+K][j+K];
            int tmp = a + b + c + d + e;
            ma = max(ma, max(tmp, sum - tmp));
        }
    }
    ma += white;
    printf("%d\n", ma);
    return 0;
}

おまけ

二次元累積和を使う問題として、他に ARC のチョコレート があります。こちらに関しても累積和の配列 つで解くことができます。