Problem:


Score : 500 points

Problem Statement

AtCoDeer is thinking of painting an infinite two-dimensional grid in a checked pattern of side K.
Here, a checked pattern of side K is a pattern where each square is painted black or white so that each connected component of each color is a K × K square.
Below is an example of a checked pattern of side 3:

AtCoDeer has N desires.
The i-th desire is represented by x_i, y_i and c_i.
If c_i is B, it means that he wants to paint the square (x_i,y_i) black; if c_i is W, he wants to paint the square (x_i,y_i) white.
At most how many desires can he satisfy at the same time?

Constraints

1 ≤ N ≤ 10^5

1 ≤ K ≤ 1000

0 ≤ x_i ≤ 10^9

0 ≤ y_i ≤ 10^9

If i ≠ j, then (x_i,y_i) ≠ (x_j,y_j).

c_i is B or W.

N, K, x_i and y_i are integers.

Input

Input is given from Standard Input in the following format:

N K
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N

Output

Print the maximum number of desires that can be satisfied at the same time.

Sample Input 1

4 3
0 1 W
1 2 W
5 3 B
5 4 B

Sample Output 1

4

He can satisfy all his desires by painting as shown in the example above.

Sample Input 2

2 1000
0 0 B
0 1 W

Sample Output 2

2

Sample Input 3

6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W

Sample Output 3

4



Sample input:
4 3
0 1 W
1 2 W
5 3 B
5 4 B


Sample output:
4

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
ws = [[0] * K for _ in range(K)]
bs = [[0] * K for _ in range(K)]
for _ in range(N):
  x, y, c = input().split()
  x = int(x)
  y = int(y)
  t = x // K + y // K
  if t % 2:
    if c == "W": c = "B"
    elif c == "B": c = "W"
  ws[y % K][x % K] += int(c == "W")
  bs[y % K][x % K] += int(c == "B")
#print(ws)
#print(bs)
csw = [[0] * (K + 1) for _ in range(K + 1)]
csb = [[0] * (K + 1) for _ in range(K + 1)]
for i in range(K):
  for j in range(K):
    csw[i + 1][j + 1] = csw[i + 1][j] + csw[i][j + 1] - csw[i][j] + ws[i][j]
    csb[i + 1][j + 1] = csb[i + 1][j] + csb[i][j + 1] - csb[i][j] + bs[i][j]
res = 0
for i in range(K + 1):
  for j in range(K + 1):
    u = csw[-1][-1] - csw[i][-1] - csw[-1][j] + csw[i][j] + csw[i][j]
    v = csb[i][-1] - csb[i][j] + csb[-1][j] - csb[i][j]
    res = max(res, u + v)
    u = csb[-1][-1] - csb[i][-1] - csb[-1][j] + csb[i][j] + csb[i][j]
    v = csw[i][-1] - csw[i][j] + csw[-1][j] - csw[i][j]
    res = max(res, u + v)
    #print(i, j, res)
print(res)

Submission status: Accepted

Solution code:
import sys

#縦k、横kのマスに移動させて考える
n, k = map(int, sys.stdin.readline().strip().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = sys.stdin.readline().strip().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

#累積和
#lx + lmx = n
lx = len(x)
graph[0][0] += lx
for i in range(lx):
    graph[x[i]][0] -= 1
    graph[0][y[i]] -= 1
    graph[x[i]][y[i]] += 2

lmx = len(mx)
graph[0][0] -= lmx
for i in range(lmx):
    graph[mx[i]][0] += 1
    graph[0][my[i]] += 1
    graph[mx[i]][my[i]] -= 2

for i in graph:
    for j in range(k-1):
        i[j+1] += i[j]

for i in range(k):
    for j in range(k-1):
        graph[j+1][i] += graph[j][i]

#最大値、最小値を取得
big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import chain
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, K: int, x: "List[int]", y: "List[int]", c: "List[str]"):
    imos = [[0] * (2 * K) for _ in range(2 * K)]

    def sq(x1: int, y1: int, x2: int, y2: int):
        x1 %= 2 * K
        x2 %= 2 * K
        y1 %= 2 * K
        y2 %= 2 * K
        if x1 > x2:
            imos[y1][0] += 1
            imos[y2][0] -= 1
            if y1 > y2:
                imos[0][0] += 1
        if y1 > y2:
            imos[0][x1] += 1
            imos[0][x2] -= 1
        imos[y1][x1] += 1
        imos[y1][x2] -= 1
        imos[y2][x1] -= 1
        imos[y2][x2] += 1

    for xi, yi, ci in zip(x, y, c):
        if ci == "B":
            bx = xi + 1
            by = yi + 1
        else:
            bx = xi - K + 1
            by = yi + 1
        sq(bx, by, bx + K, by + K)
        sq(bx + K, by + K, bx, by)

    # print(imos, file=sys.stderr)

    for i in range(2 * K):
        for j in range(1, 2 * K):
            imos[i][j] += imos[i][j - 1]

    for j in range(2 * K):
        for i in range(1, 2 * K):
            imos[i][j] += imos[i - 1][j]

    # print(imos, file=sys.stderr)
    print(max(chain(*imos)))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    c = [str()] * (N)  # type: "List[str]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        c[i] = next(tokens)
    solve(N, K, x, y, c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline
import numpy as np

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
def sum2d(i1,j1,i2,j2):
    A[i1][j1] += 1
    A[i1][j2] -= 1
    A[i2][j1] -= 1
    A[i2][j2] += 1


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,K = map(int,input().split())
XYC = [list(input().split()) for _ in range(N)]

A = [[0 for _ in range(K*2+1)] for _ in range(K*2+1)]

for x,y,c in XYC:
    # 白はそのまま, 黒はx軸方向にKずらして白として扱う
    i = (int(x) if c=="W" else int(x)+K) % (K*2)
    j = int(y) % (K*2)
    i0 = i%K
    j0 = j%K

    # 分割区画の左下が白の場合 (白は5箇所)
    #   a * b
    #   * c *
    #   d * e
    if (i<K and j<K) or (i>=K and j>=K):
        sum2d(0,0,i0,j0) # (a)左上
        sum2d(i0+K,0,K*2,j0) # (b)右上
        sum2d(i0,j0,i0+K,j0+K) # (c)真ん中
        sum2d(0,j0+K,i0,K*2) # (d)左下
        sum2d(i0+K,j0+K,K*2,K*2) # (e)右下

    # 分割区画の左下が黒の場合 (白は4箇所)
    #   * a *
    #   b * c
    #   * d *
    else:
        sum2d(i0,0,i0+K,j0) # (a)上
        sum2d(0,j0,i0,j0+K) # (b)左
        sum2d(i0+K,j0,K*2,j0+K) # (c)右
        sum2d(i0,j0+K,i0+K,K*2) # (d)下
 
# 2次元累積和
AA = np.array(A)
for i in range(K*2):
    AA[i+1, :] += AA[i, :]
for j in range(K*2):
    AA[:, j+1] += AA[:, j]
 
print(AA.max())

Submission status: Accepted

Solution code:
import numpy as np
n,k=map(int,input().split())
m=np.zeros((3*k,3*k),dtype=int)
l=2*k
o=0
for _ in range(n):
  x,y,c=input().split()
  x,y=int(x)%l,int(y)%l
  t=c=='W'
  m[x,y]+=1-2*t
  o+=t
for _ in range(2):
  m[l:]=m[:k]
  m=np.cumsum(m,axis=0)
  m[:l]=m[k:]-m[:l]
  m=m.T
m=m[:l,:l]
print(o+(m+np.roll(np.roll(m,k,axis=0),k,axis=1)).max())

Submission status: Accepted

Solution code:
# D - Checker

N, K = map(int, input().split())
g = [[0]*K for _ in range(K)] # PDF解説通り2K*2K範囲でやると市松模様の処理が大変なのでK*Kの範囲で計算

for _ in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    tmp = (x//K + y//K) % 2
    x %= K
    y %= K
    if (tmp == 0 and c == "B") or (tmp == 1 and c == "W"):
        g[x][y] += 1
    else:
        g[x][y] -= 1 # 白希望の点を-1で記録する

for i in range(K):
    for j in range(1,K):
        g[i][j] += g[i][j-1]

for i in range(1,K):
    for j in range(K):
        g[i][j] += g[i-1][j]

# [i,j]を黒範囲の左下の点とする。[0,i] * [0,j] の範囲または[i+1,K-1] * [j+1,K-1]の範囲にある黒希望点の個数を足し、白希望の点の個数を引く
# 上記範囲外にある白希望の点の個数を足し、黒希望の点の個数を引く
ans = 0
for i in range(K):
    for j in range(K):
        n_satisfied = g[-1][-1] -2*(g[-1][j] + g[i][-1]) + 4*g[i][j]
        ans = max(ans, (N + n_satisfied)//2, (N - n_satisfied)//2) # ((希望通りの点 + 希望通りでない点) + (希望通りの点 - 希望通りでない点))//2

print(ans)

Submission status: Accepted

Solution code:
import sys


N, K = map(int, input().split())
cnt_B = 0
black = [[0] * (2 * K) for _ in range(2 * K)]
for s in sys.stdin.readlines():
    x, y, c = s.split()
    x = int(x); y = int(y)
    y = y if c == 'B' else y + K
    black[x % (2 * K)][y % (2 * K)] += 1
    cnt_B += 1

S_black = [[0] * (2 * K + 1) for _ in range(2 * K)]
for i in range(2 * K):
    for j in range(2 * K):
        S_black[i][j + 1] = S_black[i][j] + black[i][j]

ans = 0
for j in range(K):
    var_B = 0
    for i in range(K):
        var_B += S_black[i][j + K] - S_black[i][j]
        var_B += S_black[i + K][2 * K] - (S_black[i + K][j + K] - S_black[i + K][j])
    ans = max(ans, max(var_B, cnt_B - var_B))

    for i in range(K):
        var_B += (S_black[i + K][j + K] - S_black[i + K][j]) - (S_black[i][j + K] - S_black[i][j])
        var_B -= S_black[i + K][2 * K] - (S_black[i + K][j + K] - S_black[i + K][j])
        var_B += S_black[i][2 * K] - (S_black[i][j + K] - S_black[i][j])
        ans = max(ans, max(var_B, cnt_B - var_B))

print(ans)

Submission status: Accepted

Solution code:
import sys


N, K = map(int, input().split())
cnt_B = 0
cnt_W = 0
black = [[0] * (2 * K) for _ in range(2 * K)]
white = [[0] * (2 * K) for _ in range(2 * K)]
for s in sys.stdin.readlines():
    x, y, c = s.split()
    x = int(x); y = int(y)
    if c == 'B':
        black[x % (2 * K)][y % (2 * K)] += 1
        cnt_B += 1
    else:
        white[x % (2 * K)][y % (2 * K)] += 1
        cnt_W += 1

S_black = [[0] * (2 * K + 1) for _ in range(2 * K)]
S_white = [[0] * (2 * K + 1) for _ in range(2 * K)]
for i in range(2 * K):
    for j in range(2 * K):
        S_black[i][j + 1] = S_black[i][j] + black[i][j]
        S_white[i][j + 1] = S_white[i][j] + white[i][j]

ans = 0
for j in range(K):
    var_B, var_W = 0, 0
    for i in range(K):
        var_B += S_black[i][j + K] - S_black[i][j]
        var_W += S_white[i][j + K] - S_white[i][j]
        
        var_B += S_black[i + K][2 * K] - (S_black[i + K][j + K] - S_black[i + K][j])
        var_W += S_white[i + K][2 * K] - (S_white[i + K][j + K] - S_white[i + K][j])

    ans = max(ans, max(var_B + (cnt_W - var_W), var_W + (cnt_B - var_B)))
    for i in range(K):
        var_B += (S_black[i + K][j + K] - S_black[i + K][j]) - (S_black[i][j + K] - S_black[i][j])
        var_W += (S_white[i + K][j + K] - S_white[i + K][j]) - (S_white[i][j + K] - S_white[i][j])

        var_B -= S_black[i + K][2 * K] - (S_black[i + K][j + K] - S_black[i + K][j])
        var_B += S_black[i][2 * K] - (S_black[i][j + K] - S_black[i][j])
        var_W -= S_white[i + K][2 * K] - (S_white[i + K][j + K] - S_white[i + K][j])
        var_W += S_white[i][2 * K] - (S_white[i][j + K] - S_white[i][j])

        ans = max(ans, max(var_B + (cnt_W - var_W), var_W + (cnt_B - var_B)))

print(ans)

Submission status: Accepted

Solution code:
def main():
    n,k=map(int,input().split())
    grid=[[0]*k for _ in range(k)]
    for i in range(n):
        x,y,c=map(lambda x:x,input().split())
        x,y=int(x),int(y)
        p=(x//k+y//k)%2
        if (p==0 and c=="B")|(p==1 and c=="W"): grid[x%k][y%k]+=1
        else: grid[x%k][y%k]-=1

    for i in range(k):
        for j in range(1,k):
            grid[i][j]+=grid[i][j-1]

    for i in range(1,k):
        for j in range(k):
            grid[i][j]+=grid[i-1][j]


    ans=0
    for i in range(k):
        for j in range(k):
            b=grid[i][j]*4+grid[k-1][k-1]-(grid[i][k-1]+grid[k-1][j])*2
            ans=max(ans,n+b,n-b)
    print(ans//2)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
grid=[[0]*k for _ in range(k)]
for i in range(n):
    x,y,c=map(lambda x:x,input().split())
    x,y=int(x),int(y)
    p=(x//k+y//k)%2
    if (p==0 and c=="B")|(p==1 and c=="W"): grid[x%k][y%k]+=1
    else: grid[x%k][y%k]-=1

for i in range(k):
    for j in range(1,k):
        grid[i][j]+=grid[i][j-1]

for i in range(1,k):
    for j in range(k):
        grid[i][j]+=grid[i-1][j]


ans=0
for i in range(k):
    for j in range(k):
        b=grid[i][j]*4+grid[k-1][k-1]-(grid[i][k-1]+grid[k-1][j])*2
        ans=max(ans,n+b,n-b)
print(ans//2)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
grid=[[0]*k for _ in range(k)]
for i in range(n):
    x,y,c=map(lambda x:x,input().split())
    x,y=int(x),int(y)
    p=(x//k+y//k)%2
    if (p==0 and c=="B")|(p==1 and c=="W"): grid[x%k][y%k]+=1
    else: grid[x%k][y%k]-=1

for i in range(k):
    for j in range(1,k):
        grid[i][j]+=grid[i][j-1]

for i in range(1,k):
    for j in range(k):
        grid[i][j]+=grid[i-1][j]


ans=0
for i in range(k):
    for j in range(k):
        b=grid[i][j]*4+grid[k-1][k-1]-(grid[i][k-1]+grid[k-1][j])*2
        ans=max(ans,(n+b)//2,(n-b)//2)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
xyc = [list(input().split()) for i in range(n)]
for i in range(n):
  x,y,c = xyc[i]
  x = int(x)
  y = int(y)
  xq = x//k
  yq = y//k
  if (xq+yq)%2:
    if c == "B":
      c = "W"
    else:
      c = "B"
  x %= k
  y %= k
  xyc[i] = x,y,c
gridw = [[0 for i in range(k+1)] for j in range(k+1)]
gridb = [[0 for i in range(k+1)] for j in range(k+1)]
for x,y,c in xyc:
  x += 1
  y += 1
  if c == "B":
    gridb[x][y] += 1
  else:
    gridw[x][y] += 1
for grid in gridb,gridw:
  for i in range(1,k+1):
    for j in range(k+1):
      grid[i][j] += grid[i-1][j]
for grid in gridb,gridw:
  for i in range(k+1):
    for j in range(1,k+1):
      grid[i][j] += grid[i][j-1]
nw = gridw[-1][-1]
nb = gridb[-1][-1]
ans = 0
def sm(grid,i,j):
  return grid[i][j]+grid[-1][-1]-grid[-1][j]-grid[i][-1]+grid[i][j]
for i in range(k+1):
  for j in range(k+1):
    x = sm(gridb,i,j)+nw-sm(gridw,i,j)
    ans = max(ans,x,n-x)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
mod = K * 2
XY = []
MAX = K * 4
imos = list2d(MAX+1, MAX+1, 0)
for i in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    x %= mod
    y %= mod
    if c == 'B':
        x += K
    for a1 in range(2):
        for a2 in range(2):
            for b in [0, K]:
                if c == 'B':
                    b = -b
                x1 = x + a1 * mod + b
                y1 = y + a2 * mod + b
                x2 = x1 + K
                y2 = y1 + K
                x1 = max(min(x1, MAX), 0)
                y1 = max(min(y1, MAX), 0)
                x2 = max(min(x2, MAX), 0)
                y2 = max(min(y2, MAX), 0)
                imos[x1][y1] += 1
                imos[x2][y2] += 1
                imos[x1][y2] -= 1
                imos[x2][y1] -= 1

for i in range(MAX+1):
    imos[i] = list(accumulate(imos[i]))
for j in range(MAX+1):
    for i in range(MAX):
        imos[i+1][j] += imos[i][j]
ans = 0
for i in range(K*2, K*4+1):
    ans = max(ans, max(imos[i][K*2:K*4+1]))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
mod = K * 2
XY = []
MAX = K * 4
acc = list2d(MAX+1, MAX+1, 0)
for i in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    x %= mod
    y %= mod
    if c == 'B':
        x += K
    for a1 in range(3):
        for a2 in range(3):
            for b in [0, K]:
                if c == 'B':
                    b = -b
                x1 = x + a1 * mod + b
                y1 = y + a2 * mod + b
                x2 = x1 + K
                y2 = y1 + K
                x1 = max(min(x1, MAX), 0)
                y1 = max(min(y1, MAX), 0)
                x2 = max(min(x2, MAX), 0)
                y2 = max(min(y2, MAX), 0)
                acc[x1][y1] += 1
                acc[x2][y2] += 1
                acc[x1][y2] -= 1
                acc[x2][y1] -= 1

for i in range(MAX+1):
    acc[i] = list(accumulate(acc[i]))
for j in range(MAX+1):
    for i in range(MAX):
        acc[i+1][j] += acc[i][j]
ans = 0
for i in range(K*2, K*4+1):
    ans = max(ans, max(acc[i][K*2:K*4+1]))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
mod = K * 2
XY = []
MAX = K*4 + 7
acc = list2d(MAX, MAX, 0)
for i in range(N):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    x %= mod
    y %= mod
    if c == 'B':
        x += K
    for a1 in range(3):
        for a2 in range(3):
            for b in [0, K]:
                if c == 'B':
                    b = -b
                x1 = x + a1 * mod + b
                y1 = y + a2 * mod + b
                x2 = x1 + K
                y2 = y1 + K
                x1 = max(min(x1, MAX-1), 0)
                y1 = max(min(y1, MAX-1), 0)
                x2 = max(min(x2, MAX-1), 0)
                y2 = max(min(y2, MAX-1), 0)
                acc[x1][y1] += 1
                acc[x2][y2] += 1
                acc[x1][y2] -= 1
                acc[x2][y1] -= 1

for i in range(MAX):
    acc[i] = list(accumulate(acc[i]))
for j in range(MAX):
    for i in range(MAX-1):
        acc[i+1][j] += acc[i][j]
mx = 0
for j in range(K*2, K*4):
    for i in range(K*2, K*4):
        mx = max(mx, acc[i][j])
print(mx)

Submission status: Accepted

Solution code:

"""
@auther: SPD_9X2
https://atcoder.jp/contests/abc086/tasks/arc089_b

考察：

まず、x,y座標を2Kで割っておいてよい。

黒白
白黒　で考え、左下(0,0)で開始。

縦軸を固定し、左に動かしていくことを考える。
すると、現在　x%K == 0　となる部分にいる希望のみ、達成・非達成が反転する

初期の達成数を記録しておき、各列で達成・非達成がいくつあるのかをリストに記録
ずらすと、現在の達成数 += 新たに達成する要求 - 非達成になる要求
となる。2*K回操作して元に戻す

縦軸の移動は各行について、どの列に要求があるのかをおいておき、その部分の達成・非達成数を反転する
各要求で高々2回しかチェックしないため、O(N + K^2)で処理できる
"""




N,K = map(int,input().split())

cansub = [ [] for i in range(2*K) ]
notsub = [ [] for i in range(2*K) ]

notlis = [0] * (2*K)
canlis = [0] * (2*K)

for i in range(N):

    x,y,c = input().split()
    x = int(x)
    y = int(y)
    x %= (2*K)
    y %= (2*K)

    if (x >= K and y >= K) or (x < K and y < K):
        nc = "W"
    else:
        nc = "B"

    if nc == c:
        cansub[x].append(y)
        canlis[y] += 1
    else:
        notsub[x].append(y)
        notlis[y] += 1



ans = 0

for i in range(2*K):

    ncan = sum(canlis)

    for j in range(2*K):

        j %= (2*K)

        ans = max(ans,ncan)
        ncan += notlis[j]
        ncan -= canlis[j]

        t = notlis[j]
        notlis[j] = canlis[j]
        canlis[j] = t

        j += K
        j %= (2*K)

        ncan += notlis[j]
        ncan -= canlis[j]

        t = notlis[j]
        notlis[j] = canlis[j]
        canlis[j] = t


    for k in cansub[i]:
        notlis[k] += 1
        canlis[k] -= 1
    for k in notsub[i]:
        notlis[k] -= 1
        canlis[k] += 1

    t = cansub[i]
    cansub[i] = notsub[i]
    notsub[i] = t

    i += K
    i %= (2*K)

    for k in cansub[i]:
        notlis[k] += 1
        canlis[k] -= 1
    for k in notsub[i]:
        notlis[k] -= 1
        canlis[k] += 1

    t = cansub[i]
    cansub[i] = notsub[i]
    notsub[i] = t

print (ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin

N, K = map(int, read.readline().split())
k = 2 * K
xyc = np.array(read.read().split(), np.str)
x = xyc[::3].astype(int)
y = xyc[1::3].astype(int)
c = xyc[2::3]

x[c == 'B'] -= K
x %= k
y %= k

grid = np.zeros((3 * K, 3 * K), np.int64)
np.add.at(grid, (x, y), 1)
np.add.at(grid, (x + K, y + K), 1)
np.subtract.at(grid, (x + K, y), 1)
np.subtract.at(grid, (x, y + K), 1)
np.cumsum(grid, axis=0, out=grid)
np.cumsum(grid, axis=1, out=grid)

p1 = grid[:K, :K] + grid[k:, k:] + grid[K:k, K:k] + grid[k:, :K] + grid[:K, k:]
p2 = grid[K:k, :K] + grid[K:k, k:] + grid[:K, K:k] + grid[k:, K:k]
print(max(p1.max(), p2.max()))

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import Counter

read = sys.stdin

N, K = map(int, read.readline().split())
k = 2 * K
xyc = np.array(read.read().split(), np.str).reshape(-1, 3)
x = xyc[:, 0].astype(int)
y = xyc[:, 1].astype(int)
c = xyc[:, 2]

x[c == 'B'] -= K
x %= k
y %= k

grid = np.zeros((3 * K, 3 * K), np.int64)
np.add.at(grid, (x, y), 1)
np.add.at(grid, (x + K, y + K), 1)
np.subtract.at(grid, (x + K, y), 1)
np.subtract.at(grid, (x, y + K), 1)
np.cumsum(grid, axis=0, out=grid)
np.cumsum(grid, axis=1, out=grid)

p1 = grid[:K, :K] + grid[k:, k:] + grid[K:k, K:k] + grid[k:, :K] + grid[:K, k:]
p2 = grid[K:k, :K] + grid[K:k, k:] + grid[:K, K:k] + grid[k:, K:k]
print(max(p1.max(), p2.max()))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def query_cumsum2d(s, x1, y1, x2, y2):
    # [x1, x2) × [y1, y2)
    if x2 < x1:
        x1, x2 = x2, x1
    if y2 < y1:
        y1, y2 = y2, y1
    return s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]

def main():
    N, K = LI()
    G = [[0 for _ in range(2*K)] for __ in range(2*K)]
    cumsum2d = [[0 for _ in range(2*K + 1)] for __ in range(2*K + 1)]
    xyc = []
    for _ in range(N):
        x, y, c =  LS()
        x = int(x)
        y = int(y)
        if c == 'W':
            x += K
        x = x % (2 * K)
        y = y % (2 * K)
        G[x][y] += 1
        xyc.append((x, y, c))
    for x in range(2*K):
        for y in range(2*K):
            cumsum2d[x+1][y+1] = (
                cumsum2d[x+1][y]
                + cumsum2d[x][y+1]
                - cumsum2d[x][y]
                + G[x][y]
            )
    ans = 0
    # import pdb
    # print('cum: ')
    # for row in cumsum2d:
    #     print(row)
    # print()
    # print('g: ')
    # for row in G:
    #     print(row)
    for x in range(K):
        for y in range(K):
            # pdb.set_trace()
            cnt = (
                  query_cumsum2d(cumsum2d, 0, 0, x, y)
                + query_cumsum2d(cumsum2d, x, y, x+K, y+K)
                + query_cumsum2d(cumsum2d, x+K, 0, 2 * K, y)
                + query_cumsum2d(cumsum2d, 0, y+K, x, 2 * K)
                + query_cumsum2d(cumsum2d, 2*K, 2*K, x+K, y+K)
            )

            ans = max(ans, cnt, N - cnt)
    print(ans)



main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,K=map(int,input().split())
L=[[0 for i in range(K*2+1)]for j in range(K*2+1)]
for i in range(N):
    x,y,c=list(input().split())
    if c=="W":
        x=int(x)+K
        y=int(y)
    else:
        x=int(x)
        y=int(y)
    L[x%(2*K)+1][y%(2*K)+1]+=1
#print(L)

for h in range(1,2*K+1):
    for w in range(1,2*K+1):
        L[h][w]=L[h-1][w]+L[h][w]
#print(L)
for h in range(1,2*K+1):
    for w in range(1,2*K+1):
        L[h][w]=L[h][w-1]+L[h][w]
#print(L)

ans=0
for h in range(1,K+1):
    for w in range(1,K+1):
        cnt=0
        for a in range(3):
            for b in range(3):
                if (a+b)%2==0:
                    HH=h+a*K
                    if h+a*K>2*K:
                        HH=2*K
                    HL=h+a*K-K
                    if h+a*K-K<0:
                        HL=0
                    WH=w+b*K
                    if w+b*K>2*K:
                        WH=2*K
                    WL=w+b*K-K
                    if w+b*K-K<0:
                        WL=0
                    cnt+=L[HH][WH]+L[HL][WL]-L[HH][WL]-L[HL][WH]
        ans=max(ans,max(cnt,N-cnt))
print(ans)

Submission status: Accepted

Solution code:
#[0,0]が白い一辺Kの四角の左下隅にあるとして，全部の希望ますが，市松模様のどの位置にいるか調べる？
#各希望マスに関して，[0,0]がどの範囲で動いても大丈夫かを調べる（グリッドが固定されているイメージ？）
#2次元累積和

import sys
input = sys.stdin.readline

N,K=map(int,input().split())
S=[[0]*(2*K+1) for _ in range(2*K+1)]


#スタート位置9箇所
dx=[0,0,K,2*K,K,0,-K,-2*K,-K,2*K,2*K,-2*K,-2*K]
dy=[0,2*K,K,0,-K,-2*K,-K,0,K,2*K,-2*K,2*K,-2*K]

#点aが(2K-1)の正方形の中にあるか?
def ch(a):
    ax=a[1]
    ay=a[0]
    if 0<=ax and ax<=2*K-1:
        if 0<=ay and ay<=2*K-1:
            return True
    return False

#4点a,b,c,dのいずれかは正方形内にある？
def ch4(a,b,c,d):
    Li=[a,b,c,d]
    for i in range(4):
        if ch(Li[i]):
            return True
    return False

#最小を0，最大を2K-1に丸める．
def app(a):
    aa=[0,0]
    for i in range(2):
        aa[i]=a[i]
        if aa[i]<0:
            aa[i]=0
        elif aa[i]>2*K-1:
            aa[i]=2*K-1
    return aa
    
#点aに対応するところにbwを与える
def paint(a,bw):
    S[a[0]][a[1]]+=bw
    return 0
    
    
    


for _ in range(N):
    sx,sy,sc=input().split()
    x=int(sx)%(2*K)
    y=int(sy)%(2*K)
    if sc=="W":
        bw=1
    else:
        bw=-1#該当箇所を-1する
        
    #スタート位置12箇所
    s=(x-(K-1),y-(K-1))
    for i in range(len(dx)):
        ld=[s[0]+dx[i],s[1]+dy[i]]#左下
        ru=[ld[0]+(K-1),ld[1]+(K-1)]#右上
        lu=[ru[0],ld[1]]
        rd=[ld[0],ru[1]]
        
        if ch4(ld,ru,lu,rd):#4点のどれかが正方形内なら
            ld=app(ld)
            ru=app(ru)
            ru[0]+=1#累積和で-1するところは領域外（1つ奥のところ）
            ru[1]+=1
            lu=[ru[0],ld[1]]
            rd=[ld[0],ru[1]]
            paint(ld,bw)
            paint(ru,bw)
            paint(lu,bw*-1)
            paint(rd,bw*-1)
            
    if bw==-1:#該当箇所が-1されているので，全部を+1する
        S[0][0]+=1
        S[-1][-1]+=1
        S[0][-1]-=1
        S[-1][0]-=1
            
            

#累積    
for i in range(2*K+1):
    for j in range(2*K):
        S[i][j+1]+=S[i][j]
        
for j in range(2*K+1):
    for i in range(2*K):
        S[i+1][j]+=S[i][j]
        
        
ans=0
for i in range(2*K+1):
    for j in range(2*K+1):
        if S[i][j]>ans:
            ans=S[i][j]
          
        
print(ans)

Submission status: Accepted

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,K=map(int,input().split())
XYC=[input().split() for i in range(N)]
for i in range(N):
    x,y,c=XYC[i]
    XYC[i]=[int(x),int(y),c]

lstB=[[0 for i in range(K)] for m in range(K)]
lstW=[[0 for i in range(K)] for m in range(K)]
for x,y,c in XYC:

    if ((x//K + y//K) + (c=="W") * 1)%2==0:
        lstB[x%K][y%K]+=1
    else:
        lstW[x%K][y%K]+=1

#print(lstB)
#print(lstW)
sumB=[sum(lstB[x]) for x in range(K)]
sumW=[sum(lstW[x]) for x in range(K)]
ruisumB=[0]
ruisumW=[0]
for i in range(0,K):
    ruisumB.append(ruisumB[i]+sumB[i])
    ruisumW.append(ruisumW[i]+sumW[i])


ruiBy=[[0] for k in range(K)]
ruiWy=[[0] for k in range(K)]
for y in range(K):
    for x in range(K):
        ruiBy[y].append(lstB[x][y]+ruiBy[y][x])
        ruiWy[y].append(lstW[x][y]+ruiWy[y][x])
Revalue=0
for x in range(K+1):
    value=0
    value+=ruisumW[x]
    value+=ruisumB[K]-ruisumB[x]
    Revalue=max(Revalue,value)
    for y in range(K):
        value+=ruiWy[y][K]-2*ruiWy[y][x]
        value-=ruiBy[y][K]-2*ruiBy[y][x]
        Revalue=max(Revalue,value)

for x in range(K+1):
    value=0
    value+=ruisumB[x]
    value+=ruisumW[K]-ruisumW[x]
    Revalue=max(Revalue,value)
    for y in range(K):
        value+=ruiBy[y][K]-2*ruiBy[y][x]
        value-=ruiWy[y][K]-2*ruiWy[y][x]
        Revalue=max(Revalue,value)

print(Revalue)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import Counter

read = sys.stdin

N, K = map(int, read.readline().split())
k = 2 * K
xyc = np.array(read.read().split(), np.str).reshape(-1, 3)
x = xyc[:, 0].astype(int)
y = xyc[:, 1].astype(int)
c = xyc[:, 2]

x[c == 'B'] -= K
x %= k
y %= k

'''
# grid[[1,1],[2,2]]+=1 としてもgrid[1,2]=1であり重複は考慮されない。
# uniqueを使って(x,y)の重複をカウントする
# return_countはver1.9からだった・・・ ダメじゃん
xy, cnt = np.unique(x + y * 10000, return_counts=True)
x = xy % 10000
y = xy // 10000
'''
xy = Counter(zip(x.tolist(), y.tolist()))
cnt = np.array(list(xy.values()), np.int64)
xy = np.array(list(xy.keys()), np.int64)
x = xy[:, 0]
y = xy[:, 1]

grid = np.zeros((3 * K, 3 * K), np.int64)
grid[x, y] += cnt
grid[x + K, y + K] += cnt
grid[x + K, y] -= cnt
grid[x, y + K] -= cnt
np.cumsum(grid, axis=0, out=grid)
np.cumsum(grid, axis=1, out=grid)

p1 = grid[:K, :K] + grid[k:, k:] + grid[K:k, K:k] + grid[k:, :K] + grid[:K, k:]
p2 = grid[K:k, :K] + grid[K:k, k:] + grid[:K, K:k] + grid[k:, K:k]
print(max(p1.max(), p2.max()))

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import Counter

read = sys.stdin

N, K = map(int, read.readline().split())
k = 2 * K
xyc = np.array(read.read().split(), np.str).reshape(-1, 3)
x = xyc[:, 0].astype(int)
y = xyc[:, 1].astype(int)
c = xyc[:, 2]

x[c == 'B'] -= K
x %= k
y %= k

'''
# grid[[1,1],[2,2]]+=1 としてもgrid[1,2]=1であり重複は考慮されない。
# uniqueを使って(x,y)の重複をカウントする
# return_countはver1.9からだった・・・ ダメじゃん
xy, cnt = np.unique(x + y * 10000, return_counts=True)
x = xy % 10000
y = xy // 10000
'''
xy = Counter(zip(x, y))
cnt = np.array(list(xy.values()), np.int64)
xy = np.array(list(xy.keys()), np.int64)
x = xy[:, 0]
y = xy[:, 1]

grid = np.zeros((3 * K, 3 * K), np.int64)
grid[x, y] += cnt
grid[x + K, y + K] += cnt
grid[x + K, y] -= cnt
grid[x, y + K] -= cnt
np.cumsum(grid, axis=0, out=grid)
np.cumsum(grid, axis=1, out=grid)

p1 = grid[:K, :K] + grid[k:, k:] + grid[K:k, K:k] + grid[k:, :K] + grid[:K, k:]
p2 = grid[K:k, :K] + grid[K:k, k:] + grid[:K, K:k] + grid[k:, K:k]
print(max(p1.max(), p2.max()))