Checker [AtCoder Regular Contest 089 / AtCoder Beginner Contest 086 D]

https://beta.atcoder.jp/contests/arc089/tasks/arc089_b

前提知識

• 2次元累積和

解法

https://beta.atcoder.jp/contests/arc089/submissions/2000826

まず同一視出来る部分を考える。
どんな白黒にしても「座標(x,y)と(x+2K,y+2K)は必ず同じ色になる」
なので、全ての座標はmod 2Kをして2K*2Kの盤面に変換することができる。

ここで白の正方形の右下を(x, y)とすると、
白は(x,y)～(x+K-1,y+K-1)の正方形と(x+K,y+K)～(x+2K-1, y+2K-1)の正方形の部分になる。
黒は(x+K,y)～(x+2K-1,y+K-1)の正方形と(x,y+K)～(x+K-1,y+2K-1)の正方形の部分になる。
白の正方形の右下(x,y)を2K*2Kの盤面について全探索を行って、上の正方形に含まれる白と黒の数の総和の最大値を答えれば良い。
全探索でO(K^2)なので、総和の計算はO(1)でやらないといけない。
このために二次元累積和を使おう。
(x,y)を全探索して累積和を取ると2K*2Kの盤面でははみ出してしまうため、二次元累積和を作るときは4K*4Kの盤面（4つ分コピーしたやつ）で累積和を作ろう。
　
下の二次元累積和のライブラリはget(sx, sy, tx, ty)で(sx,sy)～(tx,ty)の四角形の累積和を取得できる。

int N, K, X[101010], Y[101010]; string C[101010];
//---------------------------------------------------------------------------------------------------
Ruisekiwa2D<4020, 4020> BR, WR;
int B[2010][2010], W[2010][2010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    int KK = K * 2;
    rep(i, 0, N) cin >> X[i] >> Y[i] >> C[i];
 
    rep(i, 0, N) {
        if (C[i] == "B") B[Y[i] % KK][X[i] % KK]++;
        else W[Y[i] % KK][X[i] % KK]++;
    }
    rep(y, 0, 2 * KK) rep(x, 0, 2 * KK) {
        BR.set(x, y, B[y % KK][x % KK]);
        WR.set(x, y, W[y % KK][x % KK]);
    }
    BR.build();
    WR.build();
 
    int ans = 0;
    rep(y, 0, KK) rep(x, 0, KK) {
        int b = BR.get(x, y, x + K - 1, y + K - 1) + BR.get(x + K, y + K, x + KK - 1, y + KK - 1);
        int w = WR.get(x + K, y, x + KK - 1, y + K - 1) + WR.get(x, y + K, x + K - 1, y + KK - 1);
        int sm = b + w;
        chmax(ans, sm);
    }
    cout << ans << endl;
}