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:
# -*- 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]を初期化する値
        mat[row][col]+=val
        """
        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 __str__(self):
        return "\n".join(map(str, [v for v in self.mat]))


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
    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()

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:
N, K = map(int, input().split())
T = [[0] * (2 * K + 5) for i in range(2 * K + 5)]
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        y += K
    T[x % (2 * K) + 1][y % (2 * K) + 1] += 1

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


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


num = 0
for i in range(K + 1):
    for j in range(K + 1):
        d = T[i][j]
        d += T[i + K][j + K] - T[i][j + K] - T[i + K][j] + T[i][j]
        d += T[2 * K][j] - T[i + K][j]
        d += T[i][2 * K] - T[i][j + K]
        d += T[2 * K][2 * K] - T[2 * K][j + K] - T[i + K][2 * K] + T[i + K][j + K]
        num = max(num, d)
        num = max(num, N - d)

print(num)

Submission status: Accepted

Solution code:
from itertools import accumulate
from operator import add
 
N, K = map(int, input().split())
K2 = 2 * K
 
# Gss[i][j]: 「市松模様の黒い部分の右上のマス」が(i,j)のとき、満たせる要望の個数
Gss = [[0] * K2 for i in range(K2)]
 
for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
 
    # 要望を「0<=x<2K, 0<=y<K, 'B'」に変換する
    if c == 'W':
        x -= K
    x, y = x % K2, y % K2
 
    if y >= K:
        x, y = (x - K) % K2, y - K
 
    # 要望を満たす「市松模様の黒い部分の右上のマス」に対して、+1する
    # （後で累積和を取る）
    Gss[x][y] += 1
    Gss[x][y - K] += -1
    if x != K:
        Gss[x - K][y - K] += 1
        Gss[x - K][y] += -1
    if x > K:
        Gss[0][y] += 1
        Gss[0][y - K] += -1
 
# 累積和を取る
Gss = [accumulate(Gs) for Gs in Gss]
Gss = [accumulate(Gs) for Gs in zip(*Gss)]
Gss = list(map(list, zip(*Gss))) # 転置
 
# 「K<=y<2K」の部分を、「0<=y<K」に重ね合わせる
Gss = [map(add, Gss[i][:K], Gss[i - K][K:]) for i in range(K2)]
 
# Gssの最大値が答え
print(max(map(max, Gss)))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
white = [[0 for _ in range(2*k+1)] for _ in range(2*k+1)]

for _ in range(n):
	x, y, c = input().split()
	x, y = (int(x) - 1) % (2*k), (int(y) - 1) % (2*k)
	if (c == "B"):
		x = (x-k) % (2*k)

	if not ((x<k) ^ (y<k)):
		if y >= k:
			x, y = x-k, y-k
		white[0][0] += 1
		white[x][0] += -1
		white[x+k][0] += -1
		white[2*k][0] += 1
		white[0][y] += -1
		white[x][y] += 2
		white[x+k][y] += -2
		white[2*k][y] += 1
		white[0][y+k] += 1
		white[x][y+k] += -2
		white[x+k][y+k] += 2
		white[2*k][y+k] += -1
		white[0][2*k] += -1
		white[x][2*k] += 1
		white[x+k][2*k] += -1
		white[2*k][2*k] += 1

	else:
		if y >= k:
			x, y = x+k, y-k
		white[x-k][0] += 1
		white[x][0] += -1
		white[0][y] += 1
		white[x-k][y] += -2
		white[x][y] += 2
		white[2*k][y] += -1
		white[0][y+k] += -1
		white[x-k][y+k] += 2
		white[x][y+k] += -2
		white[2*k][y+k] += 1
		white[x-k][2*k] += -1
		white[x][2*k] += 1

#print(white)

for i in range(2*k+1):
	for j in range(2*k):
		white[i][j+1] += white[i][j]

for j in range(2*k+1):
	for i in range(2*k):
		white[i+1][j] += white[i][j]

#print(white)

ans = 0
for i in range(2*k):
	for j in range(2*k):
		ans = max(ans, white[i][j])

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
dK = 2*K

MeetDemand =[[0 for y in range(dK+1)] for x in range(K+1)]
for i in range(N):
    x, y, c =input().split()
    x = int(x) % dK
    y = (int(y)+K if c=="W" else int(y)) % dK
    if K <= x:
        if 0 <= y < K:
            x -= K
            y += K
        else:
            x %= K
            y %= K
    if 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
        MeetDemand[0][y+K+1] += 1
        MeetDemand[x+1][y+K+1] -= 2
    else:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][y+1] += 2

for x in range(K):
    for y in range(1, dK):
        MeetDemand[x][y] += MeetDemand[x][y-1]
for y in range(dK):
    for x in range(1, K):
        MeetDemand[x][y] += MeetDemand[x-1][y]

Ans = max(MeetDemand[0][:dK])
for i in range(1, K):
    Ans = max(Ans, max(MeetDemand[i][:dK]))
print(Ans)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    xycs = [input().split() for _ in range(n)]
    tbl = [[0 for _ in range(k*2+1)] for _ in range(k+1)]
    
    for sx, sy, c in xycs:
        rx, ry = map(int, (sx, sy))
        mx, my = (rx-1) % (2*k), (ry-1) % (2*k)
        dx, dy = (mx + is_black(c)*k + (my<k)*k) % (2*k), my%k

        if dx < k:
            tbl[0][0] += 1
            tbl[0][dx+1] -= 1
            tbl[dy+1][0] -= 1
            tbl[dy+1][dx+1] += 2

            tbl[0][dx+1+k] += 1
            tbl[dy+1][dx+1+k] -= 2
        else:
            dx = dx % k
            tbl[0][dx+1] += 1
            tbl[dy+1][0] += 1
            tbl[dy+1][dx+1] -= 2

            tbl[0][dx+1+k] -= 1
            tbl[dy+1][dx+1+k] += 2
    for i in range(k):
        for j in range(1, 2*k):
            tbl[i][j] += tbl[i][j-1]
    for i in range(1, k):
        for j in range(0, 2*k):
            tbl[i][j] += tbl[i-1][j]
    print(max(max(t for t in ts) for ts in tbl[:k][:2*k]))

def is_black(c):
    return 1 if c=='B' else 0

main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
dpw = [[0]*(4*k+1) for i in range(4*k+1)]
for i in range(n):
  x,y,c = map(str,input().split())
  x = int(x)
  y = int(y)
  if c == "W":
    dpw[x%(2*k)+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+2*k+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+1][y%(2*k)+2*k+1] += 1
  else:
    y+=k
    dpw[x%(2*k)+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+2*k+1] += 1
    dpw[x%(2*k)+2*k+1][y%(2*k)+1] += 1
    dpw[x%(2*k)+1][y%(2*k)+2*k+1] += 1
for i in range(1,4*k+1):
  for j in range(1,4*k+1):
    dpw[i][j] += dpw[i-1][j] + dpw[i][j-1]-dpw[i-1][j-1]
ans = 0
for i in range(1,2*k+1):
  for j in range(1,2*k+1):
    tmp = 0
    tmp += dpw[k+i-1][k+j-1]+dpw[i-1][j-1]-dpw[i-1][j+k-1]-dpw[i+k-1][j-1]
    tmp += dpw[k+i-1+k][k+j-1+k]+dpw[i-1+k][j-1+k]-dpw[i-1+k][j+k-1+k]-dpw[i+k-1+k][j-1+k]
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from numpy import*;N,K=map(int,input().split());m,L,o=zeros((3*K,3*K)),2*K,0
for _ in[0]*N:x,y,c=input().split();t=c=='W';m[int(x)%L,int(y)%L]+=2*t-1;o+=t
for _ in[0,0]:m[L:]=m[:K];m=cumsum(m,0);m[:L]-=m[K:];m=m.T
m=m[:L,:L];print(o-int((m+roll(roll(m,K,0),K,1)).min()))

Submission status: Accepted

Solution code:
from numpy import*
N,K=map(int,input().split())
m=zeros((3*K,3*K))
L=2*K
o=0
for _ in [0]*N:
 x,y,c=input().split()
 x,y=int(x)%L,int(y)%L
 t=c=='W'
 m[x,y]+=2*t-1
 o+=t
for _ in [0,0]:
 m[L:]=m[:K]
 m=cumsum(m,axis=0)
 m[:L]-=m[K:]
 m=m.T
m=m[:L,:L]
print(o-int((m+roll(roll(m,K,axis=0),K,axis=1)).min()))

Submission status: Accepted

Solution code:
from numpy import*
N,K=map(int,input().split())
m=zeros((3*K,3*K),dtype=int)
L=2*K
o=0
for _ in [0]*N:
 x,y,c=input().split()
 x,y=int(x)%L,int(y)%L
 t=c=='W'
 m[x,y]+=2*t-1
 o+=t
for _ in [0,0]:
 m[L:]=m[:K]
 m=cumsum(m,axis=0)
 m[:L]-=m[K:]
 m=m.T
m=m[:L,:L]
print(o-int((m+roll(roll(m,K,axis=0),K,axis=1)).min()))

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
import numpy as np

N, K = inpl()
H = np.zeros((K,K), dtype = np.int32)
for _ in range(N):
    x, y, c = input().split() 
    x = int(x)
    y = int(y)
    t = c == 'B'
    x %= 2*K
    y %= 2*K
    if x >= K:
        x -= K
        t = not t
    if y >= K:
        y -= K
        t = not t
    if t:
        H[x][y] += 1
        continue
    H[x][y] -= 1

H = H.cumsum(axis=0)
H = H.cumsum(axis=1)

checkH = H[K-1][K-1] + 2*H
for i in range(K):
            checkH[i] -= H[i][K-1]
            checkH.T[i] -= H.T[i][K-1]

Hans = (N - checkH[K-1][K-1])//2 + checkH

print(max(np.amax(Hans), N-np.amin(Hans)))

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

N, K = inpl()
import numpy as np
H = np.zeros((K,K), dtype = np.int32)
for _ in range(N):
    x, y, c = input().split() 
    x = int(x)
    y = int(y)
    t = c == 'B'
    x %= 2*K
    y %= 2*K
    if x >= K:
        x -= K
        t = not t
    if y >= K:
        y -= K
        t = not t
    if t:
        H[x][y] += 1
        continue
    H[x][y] -= 1

H = H.cumsum(axis=0)
H = H.cumsum(axis=1)

checkH = H[K-1][K-1] + 2*H
for i in range(K):
            checkH[i] -= H[i][K-1]
checkH = checkH.T 
H = H.T
for i in range(K):
            checkH[i] -= H[i][K-1]
Hans = (N - checkH[K-1][K-1])//2 + checkH

print(max(np.amax(Hans), N-np.amin(Hans)))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ss = [[0] * (4*K+2) for i in range(4*K+2)]


def query(x1, x2, y1, y2):
    return ss[x2][y2] - ss[x2][y1] - ss[x1][y2] + ss[x1][y1]


def main():
    for i in range(N):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == 'W':
            y += K

        x, y = x % (2*K) + 1, y % (2*K) + 1

        ss[x][y] += 1
        ss[x+2*K][y] += 1
        ss[x][y+2*K] += 1
        ss[x+2*K][y+2*K] += 1

    for i in range(4*K+2):
        for j in range(4*K+1):
            ss[i][j+1] += ss[i][j]

    for i in range(4*K+1):
        for j in range(4*K+2):
            ss[i+1][j] += ss[i][j]

    ans = 0
    for i in range(1, 2*K+1):
        for j in range(1, 2*K+1):
            ans = max(ans, query(i, i+K, j, j+K)+query(i+K, i+2*K, j+K, j+2*K))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
B = [[0] * (2 * K) for _ in range(2 * K)]
for _ in range(N):
    x, y, c = input().split()
    if c == 'B':
        B[int(x) % (2 * K)][int(y) % (2 * K)] += 1
    else:
        B[int(x) % (2 * K)][(int(y) + K) % (2 * K)] += 1

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

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

B = [[0] * (2 * K + 1)] + [[0] + row for row in B]
ans = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        # 左上
        tmp = B[i - 1][j - 1]
        # 右上
        tmp += B[i - 1][2 * K] - B[i - 1][j + K - 1]
        # 真ん中
        tmp += B[i + K - 1][j + K - 1] - B[i - 1][j + K - 1] \
               - B[i + K - 1][j - 1] + B[i - 1][j - 1]
        # 左下
        tmp += B[2 * K][j - 1] - B[i + K - 1][j - 1]
        # 右下
        tmp += B[-1][-1] - B[i + K - 1][2 * K] - B[2 * K][j + K - 1] \
               + B[i + K - 1][j + K - 1]
        ans = max(ans, tmp, N - tmp)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
    n, k = map(int, input().split())
    xn = []
    yn = []
    for i in range(n):
        x, y, c = input().split()
        x = int(x)
        y = int(y)
        assert c in ["W", "B"]
        if c == "W":
            y += k
        xn.append(x % (2 * k))
        yn.append(y % (2 * k))

    kibou = [[0 for x in range(2 * k + 1)] for y in range(2 * k + 1)]
    for i in range(n):
        x = xn[i]
        y = yn[i]
        squares = get_list_squares(x, y, k)
        for x1, y1, x2, y2 in squares:
            kibou[y1][x1] += 1
            kibou[y1][x2] -= 1
            kibou[y2][x1] -= 1
            kibou[y2][x2] += 1

    rui = ruiseki_2d(kibou, k)
    ma = [max(rui[y]) for y in range(2 * k)]
    print(max(ma))

def get_list_squares(x, y, k):
    # (x, y) of lower bottom
    twok = 2 * k
    assert 0 <= x < twok
    assert 0 <= y < twok
    if x >= k:
        x -= k
        y = (y + k) % (twok)
    xp = x + k
    yp = (y + k) % (twok)
    li = []
    if y < yp:
        li.append((x, y, xp, yp))
        li.append((xp, yp, twok, twok))
        if y != 0:
            li.append((xp, 0, twok, y))
        if x != 0:
            li.append((0, yp, x, twok))
        if x != 0 and  y != 0:
            li.append((0, 0, x, y))
    else:
        li.append((x, y, xp, twok))
        li.append((xp, yp, twok, y))
        if x != 0:
            li.append((0, yp, x, y))
        if y != 0:
            li.append((x, 0, xp, yp))
    return li

def ruiseki_2d(kibou, k):
    rui_1d = [[0 for x in range(2 * k)] for y in range(2 * k)]
    for y in range(k * 2):
        rui_1d[y][0] = kibou[y][0]
        for x in range(1, 2 * k):
            rui_1d[y][x] = rui_1d[y][x - 1] + kibou[y][x]

    rui_2d = [[0 for x in range(2 * k)] for y in range(2 * k)]
    for x in range(2 * k):
        rui_2d[0][x] = rui_1d[0][x]
        for y in range(1, 2 * k):
            rui_2d[y][x] = rui_2d[y - 1][x] + rui_1d[y][x]
    return rui_2d

def debug_print(arr, k):
    for y in reversed(range(2 * k)):
        print(arr[y])

main()

Submission status: Accepted

Solution code:
def cl(i1,j1,i2,j2):
  if i1>i2 or j1>j2 or i1<0 or j1<0 or i2<0 or j2<0:
    return 0
  v=l[i2][j2]
  if i1>0:
    v-=l[i1-1][j2]
  if j1>0:
    v-=l[i2][j1-1]
  if i1>0 and j1>0:
    v+=l[i1-1][j1-1]
  return v

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

for i in range(N):
  xi,yi,ci=input().split()
  xi,yi=int(xi),int(yi)
  if ci=="W":yi+=K
  l[xi%K2][yi%K2]+=1

for y in range(K2):
  for x in range(1,K2):
    l[x][y]+=l[x-1][y]
for y in range(1,K2):
  for x in range(K2):
    l[x][y]+=l[x][y-1]

ans=0
for i in range(K):
  for j in range(K):
    tmp=0
    tmp+=cl(0,0,i-1,j-1)
    tmp+=cl(0,j+K,i-1,K2-1)
    tmp+=cl(i+K,j+K,K2-1,K2-1)
    tmp+=cl(i+K,0,K2-1,j-1)
    tmp+=cl(i,j,i+K-1,j+K-1)
    ans = max(ans,tmp,N-tmp)
print(ans)

Submission status: Accepted

Solution code:
def get(i1, j1, i2, j2):
  if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
    return 0
  elif i1 > 0 and j1 > 0:
    return l[i2][j2] - l[i1-1][j2] - l[i2][j1-1] + l[i1-1][j1-1]
  elif i1 <= 0 < j1:
    return l[i2][j2] - l[i2][j1-1]
  elif j1 <= 0 < i1:
    return l[i2][j2] - l[i1 - 1][j2]
  else:
    return l[i2][j2]

N, K = map(int, input().split())
K2 = 2*K
R = []
l=[[0] * K2 for _ in range(K2)]

for i in range(N):
  xi, yi, ci = input().split()
  if ci == "W":
    yi = int(yi) + K
  xi, yi = int(xi), int(yi)
  l[xi%K2][yi%K2]+=1

for y in range(K2):
  for x in range(1,K2):
    l[x][y] += l[x-1][y]
for y in range(1,K2):
  for x in range(K2):
    l[x][y] += l[x][y-1]

ans = 0
for i in range(K):
  for j in range(K):
    tmp = 0
    tmp += get(0, 0, i-1, j-1)
    tmp += get(0, j+K, i-1, K2-1)
    tmp += get(i+K, j+K, K2-1, K2-1)
    tmp += get(i+K, 0, K2-1, j-1)
    tmp += get(i, j, i+K-1, j+K-1)

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
K2 = 2*K
R = []

# (x, y) と (x, y+K)の色は必ず異なるので、すべて黒の要求に変換できる。
# 2Kずらすと必ず色が同じになるので、2Kでmodをとってよい。
for i in range(N):
    xi, yi, ci = input().split()
    if ci == "W":
        yi = int(yi) + K

    xi, yi = int(xi), int(yi)
    R.append([yi % K2, xi % K2])


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        # 問題によってイメージしやすいよう書き換えてください
        for x, y in points:
            self.G[x][y] += 1

        self.calc()

    def load_imos(self, points):
        # pointsは[[左上h, 左上w, 右下h, 右下w], ...]であること
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  # 左上
            if j2 + 1 < self.W:  # 右上
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  # 左下
            if j2 + 1 < self.W and i2 + 1 < self.H:  # 右下
                self.G[i2+1][j2+1] += 1

        self.calc()

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(K2, K2)
R2D.load(R)

ans = 0
for i in range(K):
    for j in range(K):
        tmp = 0
        tmp += R2D.get(0, 0, i-1, j-1)  # 左上
        tmp += R2D.get(0, j+K, i-1, K2-1)  # 右上
        tmp += R2D.get(i+K, j+K, K2-1, K2-1)  # 右下
        tmp += R2D.get(i+K, 0, K2-1, j-1)  # 左下
        tmp += R2D.get(i, j, i+K-1, j+K-1)  # 真ん中

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

Submission status: Accepted

Solution code:
from itertools import accumulate
from operator import add

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

# Gss[i][j]: 「市松模様の黒い部分の右上のマス」が(i,j)のとき、満たせる要望の個数
Gss = [[0] * K2 for i in range(K2)]

for i in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)

    # 要望を「0<=x<2K, 0<=y<K, 'B'」に変換する
    if c == 'W':
        x -= K
    x, y = x % K2, y % K2

    if y >= K:
        x, y = (x - K) % K2, y - K

    # 要望を満たす「市松模様の黒い部分の右上のマス」に対して、+1する
    # （後で累積和を取る）
    Gss[x][y] += 1
    Gss[x][y - K] += -1
    if x != K:
        Gss[x - K][y - K] += 1
        Gss[x - K][y] += -1
    if x > K:
        Gss[0][y] += 1
        Gss[0][y - K] += -1

# 累積和を取る
Gss = [accumulate(Gs) for Gs in Gss]
Gss = [accumulate(Gs) for Gs in zip(*Gss)]
Gss = list(map(list, zip(*Gss))) # 転置

# 「K<=y<2K」の部分を、「0<=y<K」に重ね合わせる
Gss = [map(add, Gss[i][:K], Gss[i - K][K:]) for i in range(K2)]

# Gssの最大値が答え
print(max(map(max, Gss)))

Submission status: Accepted

Solution code:
def d_checker(N, K, Q):
    # マス(x,y)が白⇔マス(x,y+K)が黒なので、希望の色がすべて黒になるようにする
    # 市松模様の周期は2Kなので、x,y座標をそれぞれ2Kで剰余を取った座標と同一視できる
    mat = [[0]*(2*K+2) for _ in range(2*K+2)]
    total = [[0]*(4*K+2) for _ in range(4*K+2)]
    for x, y, c in Q:
        if c == 'W':
            y += K
        mat[(x % (2*K)) + 1][(y % (2*K)) + 1] += 1

    # 事前に累積和を取る
    for x in range(1, 4*K+1):
        for y in range(1, 4*K+1):
            total[x][y] = total[x][y-1] + \
                mat[((x-1) % (2*K)) + 1][((y-1) % (2*K)) + 1]
    for y in range(1, 4*K+1):
        for x in range(1, 4*K+1):
            total[x][y] += total[x-1][y]

    def get(x, y):
        # 市松模様の橋の黒の座標を決めたときに実現できる希望の数
        return total[x+K-1][y+K-1] + total[x-1][y-1] - total[x-1][y+K-1] - total[x+K-1][y-1]

    ans = 0
    for x in range(1, 2*K+1):
        for y in range(1, 2*K+1):
            ans = max(ans, get(x, y)+get(x+K, y+K))
    return ans

N, K = [int(i) for i in input().split()]
Q = [(int(x), int(y), c)
    for x, y, c in [input().split() for i in range(N)]]
print(d_checker(N, K, Q))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
table=[[0]*K for i in range(K)]#W=1
C=0
for i in range(N):
    x,y,z=input().split()
    x = int(x)
    y=int(y)
    if z=='B':
        y +=K
    x %=(2*K)
    y %=(2*K)
    t = (x//K +y//K)%2
    x%= K
    y%=K
    if t:
        table[y][x]-=1
    else:
        table[y][x]+=1
        C+=1
B=N-C
#print(table)
pr=[[0]*(K+1) for i in range(K)]
for i in range(K):
    for j in range(K):
        pr[j][i+1]=pr[j][i]+table[j][i]
#print(pr)
pr2=[[0]*(K+1) for i in range(K+1)]
for j in range(K):
    for i in range(K):
        pr2[j+1][i+1]=pr2[j][i+1]+pr[j][i+1]
#print(pr2)
ans = 0
for i in range(K+1):
    for j in range(K+1):
        #s=pr2[K][K]-pr2[i-1][K] -pr2[K][j-1]+2*pr2[i-1][j-1]
        s =pr2[i][K] +pr2[K][j]-2*pr2[i][j]
        #白で塗った時に差し引き難点もらえるか
        #t=pr2[K][K]-s#黒で塗る
        #print(s,t,s-t,C-s)
        ans = max(ans,C-s,B+s)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def cumulative_sum_2d(a):
    h, w = len(a), len(a[0])
    for i in range(1, h):
        for j in range(w):
            a[i][j] += a[i-1][j]
    for i in range(h):
        for j in range(1, w):
            a[i][j] += a[i][j-1]

def solve(f):
    n, k = f.read_int_list()
    b = [[0] * k for _ in xrange(k)]
    w = [[0] * k for _ in xrange(k)]
    for i in xrange(n):
        x, y, c = f.read_str().split()
        x, y = int(x)%(2*k), int(y)%(2*k)
        sgn = 1 if c == 'B' else -1
        if x >= k:
            x -= k
            sgn *= -1
        if y >= k:
            y -= k
            sgn *= -1
        if sgn == 1:
            b[x][y] += 1
        else:
            w[x][y] += 1

    cumulative_sum_2d(b)
    cumulative_sum_2d(w)

    ans = 0
    for xi in xrange(k):
        for yi in xrange(k):
            res = 0
            if xi == yi == 0:
                res += b[k-1][k-1]
            elif xi == 0:
                res += b[k-1][k-1] - b[k-1][yi-1]
                res += w[k-1][yi-1]
            elif yi == 0:
                res += b[k-1][k-1] - b[xi-1][k-1]
                res += w[xi-1][k-1]
            else:
                res += b[k-1][k-1] - b[xi-1][k-1] - b[k-1][yi-1] + b[xi-1][yi-1]
                res += b[xi-1][yi-1]
                res += w[xi-1][k-1] - w[xi-1][yi-1]
                res += w[k-1][yi-1] - w[xi-1][yi-1]
            ans = max(res, ans)

    for xi in xrange(k):
        for yi in xrange(k):
            res = 0
            if xi == yi == 0:
                res += w[k-1][k-1]
            elif xi == 0:
                res += w[k-1][k-1] - w[k-1][yi-1]
                res += b[k-1][yi-1]
            elif yi == 0:
                res += w[k-1][k-1] - w[xi-1][k-1]
                res += b[xi-1][k-1]
            else:
                res += w[k-1][k-1] - w[xi-1][k-1] - w[k-1][yi-1] + w[xi-1][yi-1]
                res += w[xi-1][yi-1]
                res += b[xi-1][k-1] - b[xi-1][yi-1]
                res += b[k-1][yi-1] - b[xi-1][yi-1]
            ans = max(res, ans)

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def reads():
  return [int(x) for x in input().split()]

(N, K) = reads()

L = K

board = [[0] * K for _ in range(K)]

NW = 0
for _ in range(N):
    (x, y, c) = input().split()
    (x, y) = (int(x), int(y))
    c = (x // K + y // K + int(c == "W")) & 1 # W -> 1, B -> 0
    (x, y) = (x % K, y % K)
    NW += c
    board[y][x] += 1 if c == 1 else -1 # W - B
NB = N - NW

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

for i in range(K):
    for j in range(K):
        psumr[i][j+1] = psumr[i][j] + board[i][j]

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

for i in range(K):
    for j in range(K):
        psum[i+1][j+1] = psum[i][j+1] + psumr[i][j+1]

result = 0
for i in range(K+1):
    for j in range(K+1):
        summ = psum[i][K] + psum[K][j] - 2 * psum[i][j]
        result = max(result, NB + summ, NW - summ)
print(result)

Submission status: Accepted

Solution code:
def calc(K, xyc):
    K2 = K * 2
    N = len(xyc)

    p = [[0] * K2 for i in range(K2)]
    for x, y, c in xyc:
        y += c * K
        p[x % K2][y % K2] += 1
        p[(x + K) % K2][(y + K) % K2] += 1

    def calcsum(xs):
        r = sum(xs[:K])
        yield r
        for a, b in zip(xs[:K], xs[K:]):
            r += -a + b
            yield r

    pksum = [list(calcsum(xs)) for xs in p]

    rmax = N / 2
    for y in range(K):
        rcount = sum(row[y] for row in pksum[:K])
        for x in range(K):
            rmax = max(rmax, rcount, N - rcount)
            rcount += -pksum[x][y] + pksum[x + K][y]

    return rmax

if __name__ == '__main__':
    N, K = [int(e) for e in input().split()]
    xyc = [(int(x), int(y), c == "W") for x, y, c in [input().split() for i in range(N)]]
    print(calc(K, xyc))

Submission status: Accepted

Solution code:
def calc(K, xyc):
    K2 = K * 2
    N = len(xyc)

    p = [[0] * K2 for i in range(K2)]
    for x, y, c in xyc:
        y += c * K
        p[x % K2][y % K2] += 1
        p[(x + K) % K2][(y + K) % K2] += 1

    def isum(xs):
        r = 0
        yield r
        for x in xs:
            r += x
            yield r

    psum = [list(isum(row)) for row in p]
    pksum = [[b - a for a, b in zip(row, row[K:])] for row in psum]

    rmax = N / 2
    for y in range(K):
        rcount = sum(row[y] for row in pksum[:K])
        for x in range(K):
            rmax = max(rmax, rcount, N - rcount)
            rcount += -pksum[x][y] + pksum[x + K][y]

    return rmax

if __name__ == '__main__':
    N, K = [int(e) for e in input().split()]
    xyc = [(int(x), int(y), c == "W") for x, y, c in [input().split() for i in range(N)]]
    print(calc(K, xyc))

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 [0]*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 [0,0]:
	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:
N,K = map(int,input().split())

import numpy as np
m = np.zeros((3*K,3*K), dtype=np.int32)

offset = 0

for _ in range(N):
  x,y,c = input().split()
  x,y = int(x),int(y)
  x %= 2*K
  y %= 2*K
  if c == 'B':
    m[x,y] += 1
  else:
    m[x,y] -= 1
    offset += 1

K2 = 2*K
m[K2:,:K2] = m[:K,:K2]
np.cumsum(m[:,:K2],axis=0, out=m[:,:K2])
m[:K2,:K2] = m[K:,:K2] - m[:K2,:K2]

m[:K2,K2:] = m[:K2,:K]
np.cumsum(m[:K2,:],axis=1, out=m[:K2,:])
m[:K2,:K2] = m[:K2,K:] - m[:K2,:K2]


m = m[:K2,:K2]
m += np.roll(np.roll(m,K,axis=0),K,axis=1)
print(m.max()+offset)