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)で求められる。

二次元累積和 - ei1333's page

二次元累積和
- 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)

            

        
      