Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

ARC089-D 「Checker」 (500)

beta.atcoder.jp

概要

二次元グリッド上の N個のマスについて、白と黒のいずれかの色が指定される。

二次元グリッド全体を白と黒からなる幅 Kの一松模様で一様に塗ったとき、上で指定された通りに色が塗られるマスの数の最大値を求めよ。

制約

  •  1 \leq N \leq 10^5
  •  1 \leq K \leq 10^3
  •  0 \leq x_i, y_i \leq 10^9

解説

条件の持ち方

制約から愚直に条件を二次元配列として持つことはできないので、少し工夫して持つ必要がある。

 (x, y)が白に塗られたとする。このとき (x + 2K, y) (x, y + 2K)も同様に白で塗られることになる。こんな具合に、 x, yそれぞれについて 2Kで割った余りをとっても条件は変わらない。

ここで 2K \times 2Kの配列として条件を持ってもいいが、ここではもう少し工夫することにする。

先と同様に (x, y)が白に塗られたとする。このとき、 (x + K, y) (x, y + K)は黒で塗られることになる。こんな具合に、適当に色を反転させることで最終的に K \times Kの配列として条件を持つことができる。

満たされる条件数の求め方

次に満たされる条件数の求め方を考える。これは二次元累積和を使うことで高速に求めることができる。

「右上が (x, y)の長方形内に含まれる、(条件が白のマス-条件が黒のマス)の数」を二次元累積和で求めたとする。これは指定が白マスなら+1、黒マスなら-1といった具合に記録して、imos法の要領で展開すれば求められる。

このとき、全 K^2パターンの塗り方について以下の図のようにして「条件が満たされるマスの数」が求められる。

f:id:misteer:20181023082515p:plain

しかし黒マスを減点方式にしたため、この値は「黒マスを指定している条件の数」だけ少なくなっている。よって予めこれを数えておいて足す必要がある。

実はこれだけではまだ不十分で、上の図で白黒を反転させたパターンも考える必要がある。しかしこれは難しい話ではない。全体の色が反転すれば各条件の満たされる/満たされないも全て反転される。つまり上で求めた条件数を Nから引くだけでいい。

実装例

#include <iostream>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    int x[N], y[N], c[N];

    // まずは2K * 2Kの範囲に絞る
    for (int i = 0; i < N; ++i) {
        char sc;
        cin >> x[i] >> y[i] >> sc;
        x[i] %= K * 2;
        y[i] %= K * 2;
        c[i] = (sc == 'W');
    }

    int white[K][K];
    fill(white[0], white[K], 0);
    // while[x][y] = マス(x, y)を右上とした長方形に
    //               含まれている(白マス-黒マス)の総数

    int bnum = 0;
    // 黒マスを指定する条件の数

    // K * Kの範囲に絞る
    // 座標をKで割った値の偶奇で色が変わる
    for (int i = 0; i < N; ++i) {
        c[i] += x[i] / K + y[i] / K;
        c[i] %= 2;
        x[i] %= K;
        y[i] %= K;
        white[x[i]][y[i]] += (c[i] ? 1 : -1);
        if (c[i] == 0) ++bnum;
    }

    // 2次元imosの要領で展開
    for (int x = 0; x < K; ++x) {
        for (int y = 1; y < K; ++y) {
            white[x][y] += white[x][y - 1];
        }
    }

    for (int x = 1; x < K; ++x) {
        for (int y = 0; y < K; ++y) {
            white[x][y] += white[x - 1][y];
        }
    }

    int ans = 0;
    for (int x = 0; x < K; ++x) {
        for (int y = 0; y < K; ++y) {
            // (x, y)を右上の頂点とした長方形を白く塗るパターン
            int w = white[K - 1][K - 1] - white[x][K - 1] - white[K - 1][y] + white[x][y] * 2 + bnum;

            ans = max(ans, max(w, N - w));
        }
    }

    cout << ans << endl;
    return 0;
}