ARC-89 B Checker

Abst

• ARC089のB問題 (500点) Checkerをpythonで解きました。
• pypyで提出しました。

問題

• queryとして、2Dのgridで、点の座標と色(黒orしろ)が与えられる
• gridを幅Kの正方形で白黒のチェック模様に塗る
• queryの座標と色の組み合わせを満たす個数を最大にする塗り方をしたときに、最大で何個のqueryを満たすことができる?

atcoder.jp

ポイント

• 盤面を、2K*2Kに圧縮して考えることができる。
  • (x+2Kn,y+2Km,B)は(x,y,B)と同じ。
• WとBをまとめて扱う。(editrial　から学んだ)
  • (x,y,W) は　(x,y+K,B)と同じ
• 二次元累積和を使う。
  • 区間にある点を数えるときに、効率的にできる
• チェックの開始点の全探索は K**2でできる
  • 黒の開始点で探索して、d個がqueryを満たしているときに、満たしてないのは、N-d個
  • このとき、逆に、黒としてたとこをしろと考えると、条件を満たすのがN-d個
  • このように、黒白の２通りをまとめて探索することで、2k2Kが k * kで良くなる。 (この考え天才だなーと思った)

回答方針

• 2kでの余りを計算することで、(x,y)を2K*2Kに圧縮することができる。
• 圧縮した座標で、長方形の左上の点を全探索することで、答えを求める

  

  累積和の図

  submission

# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class ACC_2D:
    """
    二次元累積わ
    """

    def __init__(self, W, H):
        """
        W:幅
        H:高さ
        """

        self.W = W
        self.H = H
        self.mat = [[0]*(W+1) for _ in range(H+1)]

    def add(self, row, col, val):
        """
        matの値を変更する(初期化)
        row:たて(0<=row<H)
        col:横(0<=col<W)
        val:mat[row][col]を初期化する値
        """
        self.mat[row+1][col+1] += val

    def build(self):
        """
        累積和を計算する
        """
        for row in range(1, self.H+1):
            for col in range(1, self.W+1):
                self.mat[row][col] += self.mat[row][col-1] + \
                    self.mat[row-1][col] - self.mat[row-1][col-1]

    def get_val(self, g_row, g_col, s_row, s_col):
        """
        ２点で囲まれる長方形の、累積和を求める
        gx,gyは含まれない
        """
        return self.mat[g_row][g_col] - self.mat[s_row][g_col] - self.mat[g_row][s_col] + self.mat[s_row][s_col]


def solve():
    N, K = map(int, input().split())
    K2 = 2*K

    ACC = ACC_2D(K2, K2)

    # handle input
    # 全てを2K*2Kに圧縮する
    for _ in range(N):
        x, y, s = input().split()
        # 2K * 2Kに収める
        x = int(x)
        y = int(y)
        if s == "W":
            y += K
        x %= K2
        y %= K2

        ACC.add(x, y, 1)

    # 累積和をとる
    ACC.build()

    ans = 0
    # 黒としてチェックする
    # dは希望に沿っている数
    # ほんとは0~2Kで探さないといけないけど、N-dをついでにチェックすることで、半分でよくなる
    for row in range(K + 1):
        for col in range(K + 1):
            # 区間に入っている点の数
            d = ACC.get_val(row+K, col, row, 0)
            d += ACC.get_val(row, col+K, 0, col)
            d += ACC.get_val(K2, col+K, row+K, col)
            d += ACC.get_val(row+K, K2, row, col+K)
            ans = max(ans, d, N-d)
    print(ans)


solve()

終わりに

• 二次元累積和のライブラリ整備できてよかった。
• あんま使う機会なさそうだけど
• BとWをまとめて扱うのと、チェック柄の開始点の全探索を2K2Kでなく、KKでできるのが、すごい!! *　色々学べる問題だった気がする。