ARC 089
C - Traveling
def check(cx, cy, t, x, y):
dx = abs(x - cx)
dy = abs(y - cy)
if dx + dy > t:
return False
if ((dx + dy) & 1) != (t & 1):
return False
return True
n = int(input())
ct, cx, cy = 0, 0, 0
for _ in range(n):
t, x, y = map(int, input().split())
result = check(cx, cy, t - ct, x, y)
if not result:
print('No')
break
ct, cx, cy = t, x, y
else:
print('Yes')
D - Checker
問題
- 無限のXY座標平面を、グリッド $K$ の市松模様に塗る
- 白黒の境界位置は自由
- 座標 $(x,y)$ を(黒/白)に塗りたいという希望が $N$ 個ある
- 最大いくつの希望を叶えられるか
- $1 \le K \le 1000$
- $1 \le x,y \le 10^5$
K=3だと ■□□□■■ ■■□□□■ ■□□□■■ ■■□□□■ □■■■□□ ■■□□□■ □■■■□□ □□■■■□ □■■■□□ □□■■■□ ■□□□■■ とか □□■■■□ とかの境界位置（塗るパターン）がある
解法
計算量の見積もり
塗るパターンは、境界位置が $x,y$ 座標に各 $K$ 通りに、どちらを黒にするかで2通りあるので、$2K^2$ 通り。この部分は総当たりで調べるしかないと勘で仮定する。
とすると、$K \le 1000$ なので、各パターンにつき $O(1)$ で、叶えられる希望数を求めないと間に合わない。
情報をまとめる
市松模様の特徴、座標の繰り返しを利用する。
- $(x,y)の色 = (x+kK, y+lK)の色$ 、ただし $k,l$ 整数、偶奇一致
- $(x,y)の色 \ne (x+kK, y+lK)の色$ 、ただし $k,l$ 整数、偶奇異なる
つまり、$K=3$ なら、希望は以下のようになる。
- $(5,3)$ を黒にしたい = $(2,0)$ を黒にしたい
- $(5,2)$ を黒にしたい = $(2,2)$ を白にしたい
これで、各希望の座標を $1 \le x,y \lt K$ の範囲にまとめられた。
二次元累積和
「白にしたい」希望と「黒にしたい」希望について個別に $K \times K$ の二次元累積和テーブルを作ると、叶えられる希望数が $O(1)$ で求められる。二次元累積和では、任意の矩形範囲にある要素数をO(1)で求められる。
- 二次元累積和
req_b[x][y]$=(0,0)$～$(x,y)$ にある「そこを黒にしたい」という希望の数req_w[x][y]$=(0,0)$～$(x,y)$ にある「そこを白にしたい」という希望の数
すると、ある $x,y$ を市松模様の境界とした時に叶えられる希望数は、
たとえばK=3, x,y=1,2とする ﾊﾟﾀｰﾝA ﾊﾟﾀｰﾝB □■■ ■□□ ■□□ □■■ ■□□ □■■
パターンAで叶えられる希望数は、以下の和となる。
- Aの図で■の範囲にある「黒にしたい」希望数
- Aの図で□の範囲にある「白にしたい」希望数
叶えられる ..■■ ...... ..■■
黒にしたい = ■.... = ■.... + ......
希望数 ■.... ■.... ......
..■■ ■■■ ■.... ...... ......
...... = ■■■ - ■.... - ■■■ + ■....
...... ■■■ ■.... ■■■ ■....
叶えられる □.... □□□ ..□□
白にしたい = ..□□ = □□□ - □....
希望数 ..□□ □□□ □....
で、黒と同様に求められる
これを黒白別で求めた合計が、パターンAでの希望数となる。
パターンBで叶えられる希望数は、「Aで叶えられない希望数」となる。
境界位置をずらし、全パターン求め、その最大値が答え。
Python
配列を回して添え字から要素を取得する処理は、Pythonはやや苦手で遅い。しかし二次元累積和を求める際は多用する。
PyPyなら余裕を持って通るが、PythonならTLEだった。でも通してる人もいるので、方法はあるのだろう。（NumPyあたり上手く使えばいいのかな？）
from itertools import accumulate
n, k = map(int, input().split())
k2 = k * 2
req_b = [[0] * k for _ in range(k)]
req_w = [[0] * k for _ in range(k)]
bc, wc = 0, 0
for i in range(n):
x, y, c = input().split()
x, y = int(x), int(y)
rx, ry = x % k2, y % k2
b = c == 'B'
if rx >= k:
rx -= k
if ry >= k:
ry -= k
else:
b = not b
elif ry >= k:
ry -= k
b = not b
if b:
req_b[rx][ry] += 1
bc += 1
else:
req_w[rx][ry] += 1
wc += 1
# 累積和の計算
req_b[0] = list(accumulate(req_b[0]))
req_w[0] = list(accumulate(req_w[0]))
for i in range(1, k):
req_b[i][0] += req_b[i - 1][0]
req_w[i][0] += req_w[i - 1][0]
for j in range(1, k):
req_b[i][j] += req_b[i][j - 1] + req_b[i - 1][j] - req_b[i - 1][j - 1]
req_w[i][j] += req_w[i][j - 1] + req_w[i - 1][j] - req_w[i - 1][j - 1]
# 各パターン走査
ans = 0
for dx in range(k):
dxk_b = req_b[dx][-1]
dxk_w = req_w[dx][-1]
for dy in range(k):
b1 = req_b[dx][dy]
b2 = bc - req_b[-1][dy] - dxk_b + b1
w1 = req_w[dx][dy]
w2 = wc - req_w[-1][dy] - dxk_w + w1
b, w = b1 + b2, w1 + w2
ans = max(ans, b + wc - w, w + bc - b)
# print(dx, dy, b, w, b + wc - w, w + bc - b)
print(ans)
itertools.accumulate の利用と、配列参照を少なくしたらpythonでも通った。
from itertools import accumulate
# 入力からreq_b,req_wを作る処理は上と同じ
# 累積和の計算
req_b = [list(accumulate(req)) for req in req_b]
req_w = [list(accumulate(req)) for req in req_w]
req_b = [list(accumulate(req)) for req in zip(*req_b)]
req_w = [list(accumulate(req)) for req in zip(*req_w)]
# 各パターン走査
ans = 0
kb, kw = req_b[-1], req_w[-1]
for dx_b, dx_w in zip(req_b, req_w):
dxk_b = dx_b[-1]
dxk_w = dx_w[-1]
for b1, w1, kyb, kyw in zip(dx_b, dx_w, kb, kw):
b = bc - kyb - dxk_b + b1 * 2
w = wc - kyw - dxk_w + w1 * 2
a = b + wc - w
ans = max(ans, a, n - a)
print(ans)
