概要

\(N\) 軒の店舗の座標と売上が与えられたとき、 \(M\) 個の地点からマンハッタン距離 \(K\) 以内にある店舗の売上合計を求める問題です。座標の範囲が比較的小さいため、座標回転と2次元累積和を組み合わせることで高速にクエリを処理します。

考察

1. 素朴な解法とその限界

各クエリ（配達拠点）に対して、すべての店舗との距離を計算すると、計算量は \(O(N \times M)\) となります。本問題では \(N, M \leq 10^5\) であるため、最大で \(10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

2. マンハッタン距離の性質と座標回転

マンハッタン距離 \(|X_i - P_j| + |Y_i - Q_j| \le K_j\) は、2次元平面上では「斜め 45 度に傾いた正方形（ひし形）」の範囲を表します。このままでは扱いづらいですが、以下の座標変換（45度回転と拡大）を行うと、軸に平行な正方形として扱うことができます。

• \(u = x + y\)
• \(v = x - y\)

この変換を用いると、2点間のマンハッタン距離は、変換後の座標 \((u, v)\) におけるチェビシェフ距離に一致します。 すなわち、条件 \(|X_i - P_j| + |Y_i - Q_j| \le K_j\) は、以下の2つの条件を同時に満たすことと同値になります。

• \(|(X_i + Y_i) - (P_j + Q_j)| \le K_j \iff |u_i - u_j| \le K_j\)
• \(|(X_i - Y_i) - (P_j - Q_j)| \le K_j \iff |v_i - v_j| \le K_j\)

これは、変換後の座標系において、中心 \((u_j, v_j)\)、一辺の長さ \(2K_j\) の「軸に平行な正方形」の内部にある点を数え上げる問題に置き換わったことを意味します。

3. 座標の範囲に注目

座標 \(X, Y\) は \(0\) 以上 \(1000\) 以下の整数です。 変換後の \(u = X + Y\) は \(0 \sim 2000\)、 \(v = X - Y\) は \(-1000 \sim 1000\) の範囲に収まります。 \(v\) にオフセット（1000）を加えて \(0 \sim 2000\) の範囲に調整すれば、約 \(2000 \times 2000\) のサイズのグリッド（2次元配列）上で累積和を利用することができます。

アルゴリズム

1. 座標変換: 各店舗の座標 \((X_i, Y_i)\) を \((u_i, v_i) = (X_i + Y_i, X_i - Y_i + 1000)\) に変換します。
2. グリッドの作成: \(2001 \times 2001\) の2次元配列を用意し、各 \((u_i, v_i)\) に売上 \(C_i\) を加算します。
3. 2次元累積和の計算: グリッドに対して2次元累積和を構築します。これにより、任意の長方形領域内の売上合計を \(O(1)\) で計算できるようになります。
4. クエリ処理: 各候補 \((P_j, Q_j, K_j)\) について：
   • 中心を \((u_j, v_j) = (P_j + Q_j, P_j - Q_j + 1000)\) とします。
   • 探索範囲を \(u \in [u_j - K_j, u_j + K_j], v \in [v_j - K_j, v_j + K_j]\) とします。
   • 範囲がグリッドの外に出る場合は、 \(0 \sim 2000\) の範囲に収まるようクリッピング（クランプ）します。
   • 2次元累積和を用いて、その範囲内の合計値を計算し、出力します。

計算量

座標の最大値を \(W = 1000\) とします。 - 時間計算量: \(O(N + M + W^2)\) - 店舗の配置: \(O(N)\) - 2次元累積和の構築: \(O(W^2)\) - クエリ回答: \(O(M)\) - 空間計算量: \(O(W^2)\) - \(2000 \times 2000\) 程度の2次元配列を保持します。

実装のポイント

• 2次元累積和のインデックス: 累積和の計算を簡略化するため、配列のサイズを少し大きめ（例: \(2002 \times 2002\)）に取り、1-indexedで扱うと境界条件の処理が楽になります。

• 範囲のクリッピング: クエリの \(K_j\) が大きい場合、計算される範囲がグリッドの添字（\(0 \sim 2000\)）を超えることがあるため、必ず max(0, ...) や min(2000, ...) で範囲を制限する必要があります。

• 高速な入出力: \(N, M\) が大きいため、Pythonの場合は sys.stdin.read().split() や sys.stdout.write を使用して入出力を高速化するのが定石です。

  ソースコード

import sys

def solve():
    # Use fast I/O to read all input data
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Convert input strings to integers
    data = list(map(int, input_data))
    
    N = data[0]
    M = data[1]
    
    # The grid will store the sales at rotated coordinates.
    # The original coordinates X, Y are in [0, 1000].
    # Rotated coordinates: u = X + Y and v = X - Y + 1000.
    # Both u and v range from 0 to 2000.
    # We use a 2002x2002 grid to allow for 1-based prefix sum indexing.
    grid = [[0] * 2002 for _ in range(2002)]
    
    ptr = 2
    for _ in range(N):
        x = data[ptr]
        y = data[ptr+1]
        c = data[ptr+2]
        ptr += 3
        
        u = x + y
        v = x - y + 1000
        # Store sales in grid[u+1][v+1] for prefix sum calculation
        grid[u + 1][v + 1] += c
        
    # Compute 2D prefix sums: S[i][j] = sum(grid[1...i][1...j])
    # Step 1: Row-wise prefix sum
    for i in range(2002):
        row = grid[i]
        for j in range(1, 2002):
            row[j] += row[j-1]
    
    # Step 2: Column-wise prefix sum
    for i in range(1, 2002):
        row = grid[i]
        prev_row = grid[i-1]
        for j in range(2002):
            row[j] += prev_row[j]
    
    results = []
    for _ in range(M):
        p = data[ptr]
        q = data[ptr+1]
        k = data[ptr+2]
        ptr += 3
        
        # Rotated center coordinates
        u_center = p + q
        v_center = p - q + 1000
        
        # The Manhattan distance condition |X-P| + |Y-Q| <= K transforms into:
        # |u - u_center| <= K and |v - v_center| <= K
        u_start = u_center - k
        u_end = u_center + k
        v_start = v_center - k
        v_end = v_center + k
        
        # Clamp ranges to the grid boundaries [0, 2000]
        if u_start < 0: u_start = 0
        if u_end > 2000: u_end = 2000
        if v_start < 0: v_start = 0
        if v_end > 2000: v_end = 2000
        
        # Check if the clamped range is valid
        if u_start > u_end or v_start > v_end:
            results.append("0")
        else:
            # Query the 2D prefix sum for the range [u_start, u_end] x [v_start, v_end]
            # Sum = S[u_end+1][v_end+1] - S[u_start][v_end+1] - S[u_end+1][v_start] + S[u_start][v_start]
            res = grid[u_end + 1][v_end + 1] - grid[u_start][v_end + 1] - grid[u_end + 1][v_start] + grid[u_start][v_start]
            results.append(str(res))
            
    # Output all results separated by newlines
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。