概要

マンハッタン距離で一定範囲内にある店舗の売上合計を、各配達拠点候補について求める問題です。座標変換により矩形領域の問題に帰着し、2次元累積和で高速に解きます。

考察

素朴なアプローチの問題点

各クエリについて全店舗を走査すると \(O(NM)\) で、最大 \(10^{10}\) 程度の計算が必要になり TLE します。

重要な気づき：マンハッタン距離の座標変換（45度回転）

マンハッタン距離 \(|X_i - P_j| + |Y_i - Q_j| \le K_j\) の範囲は、\((X, Y)\) 座標上ではひし形（菱形）の形をしています。これは扱いにくいですが、次の座標変換を行うと矩形に変換できます。

\[u = x + y, \quad v = x - y\]

この変換を行うと、マンハッタン距離の条件はチェビシェフ距離（各軸方向の差の最大値）の条件に変わります：

\[|X_i - P_j| + |Y_i - Q_j| \le K_j \iff \max(|u_i - u_j|, |v_i - v_j|) \le K_j\]

これは \((u, v)\) 平面上の軸に平行な正方形（矩形）です。具体的には：

\[u_j - K_j \le u_i \le u_j + K_j \quad \text{かつ} \quad v_j - K_j \le v_i \le v_j + K_j\]

具体例: 店舗 \((3, 2)\)、拠点 \((1, 1)\)、\(K=3\) の場合 - マンハッタン距離: \(|3-1|+|2-1|=3 \le 3\) → 配達可能 - 変換後: 店舗 \(u=5, v=1\)、拠点 \(u=2, v=0\) - \(\max(|5-2|, |1-0|) = 3 \le 3\) → 同じ結果

矩形領域の和 → 2次元累積和

矩形領域内の値の合計は、2次元累積和を前計算しておけば \(O(1)\) で求められます。

アルゴリズム

1. 座標変換: 各店舗の座標 \((x, y)\) を \((u, v) = (x+y, x-y+1000)\) に変換する（\(v\) に \(1000\) を足すのは非負にするため）
2. グリッドへの配置: 変換後の座標に売上を加算する。\(u\) の範囲は \([0, 2000]\)、\(v\) の範囲は \([0, 2000]\) なのでサイズ \(2001 \times 2001\) のグリッドを用意する
3. 2次元累積和の構築: \(\text{psum}[i][j] = \sum_{0 \le a \le i, 0 \le b \le j} \text{grid}[a][b]\) を前計算
4. 各クエリに回答: 拠点 \((p, q)\) と距離 \(k\) から矩形の範囲を計算し、累積和で \(O(1)\) で合計を求める

累積和による矩形領域の和の計算（包除原理）：

\[\text{ans} = \text{psum}[u_h][v_h] - \text{psum}[u_l\!-\!1][v_h] - \text{psum}[u_h][v_l\!-\!1] + \text{psum}[u_l\!-\!1][v_l\!-\!1]\]

計算量

• 時間計算量: \(O(S^2 + M)\)（\(S = 2001\) はグリッドサイズ。累積和の構築に \(O(S^2)\)、各クエリに \(O(1)\)）
• 空間計算量: \(O(S^2)\)

実装のポイント

• \(v\) のオフセット: \(v = x - y\) は負になりうる（最小 \(-1000\)）ため、\(+1000\) して非負にする

• 範囲のクリッピング: クエリの矩形がグリッド外にはみ出す場合、\(\max\) や \(\min\) で \([0, 2000]\) に収める

• 累積和の境界処理: \(u_l = 0\) や \(v_l = 0\) のとき、添字 \(-1\) を参照しないよう条件分岐する

• 高速入力: sys.stdin.buffer.read() でまとめて読み込むことで Python でも十分高速に動作する

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1

    SIZE = 2001
    grid = [[0] * (SIZE + 1) for _ in range(SIZE + 1)]

    for i in range(N):
        x = int(input_data[idx]); idx += 1
        y = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        u = x + y
        v = x - y + 1000
        grid[u][v] += c

    # Build 2D prefix sum
    psum = [[0] * (SIZE + 1) for _ in range(SIZE + 1)]
    for i in range(SIZE):
        row_sum = 0
        for j in range(SIZE):
            row_sum += grid[i][j]
            psum[i][j] = row_sum + (psum[i - 1][j] if i > 0 else 0)

    out = []
    for j in range(M):
        p = int(input_data[idx]); idx += 1
        q = int(input_data[idx]); idx += 1
        k = int(input_data[idx]); idx += 1

        u_lo = p + q - k
        u_hi = p + q + k
        v_lo = p - q - k + 1000
        v_hi = p - q + k + 1000

        u_lo = max(u_lo, 0)
        u_hi = min(u_hi, SIZE - 1)
        v_lo = max(v_lo, 0)
        v_hi = min(v_hi, SIZE - 1)

        if u_lo > u_hi or v_lo > v_hi:
            out.append('0')
            continue

        ans = psum[u_hi][v_hi]
        if u_lo > 0:
            ans -= psum[u_lo - 1][v_hi]
        if v_lo > 0:
            ans -= psum[u_hi][v_lo - 1]
        if u_lo > 0 and v_lo > 0:
            ans += psum[u_lo - 1][v_lo - 1]
        out.append(str(ans))

    sys.stdout.write('\n'.join(out) + '\n')

main()

この解説は claude4.6opus-thinking によって生成されました。