D - Checker AtCoder Regular Contest 089 - バイトの競プロメモ

問題概略

N個の座標と希望が与えられる。

盤面をK*Kの市松模様で塗るトキ、最大でいくつの希望を叶えられるか

$1$ $\leq$ $N$ $\leq$ $10^{5}$
$1$ $\leq$ $K$ $\leq$ $1000$
$0$ $\leq$ $x_{i}$ $\leq$ $10^{9}$
$0$ $\leq$ $y_{i}$ $\leq$ $10^{9}$
$i$ $\neq$ $j$ なら $(x_{i}, y_{i})$ $\neq$ $(x_{j}, y_{j})$
$c_{i}$ は B または W
$N, K, x_{i}, y_{i}$ は整数

解法

2K周期で同じ色なので、4K*4Kの中にまとめられる。

白色の場合K動かして黒色にして、黒の累積和を持っておけば、K*Kの塗り方に対して希望がo(1)で求められる

public static void main(String[] args)
{
    N = sc.nextInt();
    K = sc.nextInt();
    long[][] b = new long[2 * K][2 * K];
    for (int i = 0; i < N; i++)
    {
        int x = sc.nextInt();
        int y = sc.nextInt();
        char c = sc.next().charAt(0);
        if (c == 'W') y += K;
        x %= 2 * K;
        y %= 2 * K;
        b[y][x]++;
    }
    long maxRes = 0;
    RectangleSum rec = new RectangleSum(b);
    //黒を動かすことだけ考える。
    //シロをうごかしたさいの数はN-それ
    for (int mh = 0; mh < K; mh++)
    {
        for (int mw = 0; mw < K; mw++)
        {
            //左上
            long res1 = rec.getSum(0, mw, 0, mh);
            //左下
            res1 += rec.getSum(0, mw, K + mh, 2 * K);
            //右上
            res1 += rec.getSum(K + mw, 2 * K, 0, mh);
            //右下
            res1 += rec.getSum(K + mw, 2 * K, K + mh, 2 * K);
            //真ん中
            res1 += rec.getSum(mw, K + mw, mh, K + mh);
            long res2 = N - res1;
            maxRes = Math.max(maxRes, res1);
            maxRes = Math.max(maxRes, res2);
        }
    }
    System.out.println(maxRes);
}

//値を渡す際は半開区間
static class RectangleSum
{
    //半開区間 0は0
    static long[][] rui;
    static int H, W;

    RectangleSum(long[][] ori)
    {
        H = ori.length;
        W = ori[0].length;
        rui = new long[H + 1][W + 1];
        for (int hi = 0; hi < H; hi++)
        {
            for (int wi = 0; wi < W; wi++)
            {
                rui[hi + 1][wi + 1] = ori[hi][wi];
            }
        }
        for (int hi = 1; hi < H + 1; hi++)
        {
            for (int wi = 1; wi < W + 1; wi++)
            {
                rui[hi][wi] += rui[hi - 1][wi];
                rui[hi][wi] += rui[hi][wi - 1];
                rui[hi][wi] -= rui[hi - 1][wi - 1];
            }
        }
    }

    //半開区間
    public static long getSum(int left, int right, int top, int bottom)
    {
        long res = rui[bottom][right];
        res -= rui[top][right];
        res -= rui[bottom][left];
        res += rui[top][left];
        return res;
    }

}