概要

高橋君の現在地 \((X_A, Y_A)\) から、半径 \(R\) 以内の距離にある花火の打ち上げ地点をすべて特定し、それらの満足度 \(P_i\) の合計を求める問題です。

考察

この問題の核心は、「2点間の距離が \(R\) 以下であるか」をいかに正確かつ効率的に判定するかという点にあります。

1. 距離の判定方法

2点 \((X_A, Y_A)\) と \((X_i, Y_i)\) のユークリッド距離は、以下の公式で求められます。 $\(\sqrt{(X_i - X_A)^2 + (Y_i - Y_A)^2}\)\( 条件は「この距離が \)R\( 以下であること」なので、式にすると以下のようになります。 \)\(\sqrt{(X_i - X_A)^2 + (Y_i - Y_A)^2} \leq R\)$

しかし、このまま計算すると「平方根（ルート）」を用いることになります。プログラミングにおいて浮動小数点数（小数）の計算には精度誤差がつきものであり、距離が \(R\) に非常に近い場合に判定を誤る可能性があります。

そこで、両辺を2乗して比較することで、整数のみで判定を行うことができます。 $\((X_i - X_A)^2 + (Y_i - Y_A)^2 \leq R^2\)$ この式を使えば、誤差を気にすることなく正確に判定が可能です。

2. 計算量と制約の確認

花火の数 \(N\) は最大 \(2 \times 10^5\) です。各花火に対して上記の計算を行うのは \(O(1)\) なので、全体で \(O(N)\) の計算量となります。これは一般的な競技プログラミングの実行時間制限（2秒程度）に対して十分に高速です。

アルゴリズム

1. 入力から高橋君の座標 \((X_A, Y_A)\)、半径 \(R\)、各花火の情報 \((X_i, Y_i, P_i)\) を読み込む。
2. 判定基準となる半径の2乗 \(R^2\) をあらかじめ計算しておく。
3. 満足度の合計を保持する変数 total_satisfaction を \(0\) で初期化する。
4. 各花火について以下を繰り返す：
   • \(X\) 方向の差 \(dx = X_i - X_A\) を計算する。
   • \(Y\) 方向の差 \(dy = Y_i - Y_A\) を計算する。
   • 距離の2乗 \(dist\_sq = dx^2 + dy^2\) を計算する。
   • \(dist\_sq \leq R^2\) であれば、total_satisfaction に \(P_i\) を加算する。
5. 最終的な total_satisfaction を出力する。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の花火を一度ずつ走査するため、入力サイズに比例した時間で終了します。
• 空間計算量: \(O(N)\)
  • すべての入力を一度に読み込む場合、リストの保持に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が \(2 \times 10^5\) と大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() などで一括して読み込む方が実行時間を短縮できます。

• 大きな整数の扱い: 座標の差の2乗は最大で \((2 \times 10^9)^2 = 4 \times 10^{18}\) 程度になります。Pythonは標準で多倍長整数をサポートしているため、オーバーフローを気にせず計算できます。

• 精度の維持: 考察で述べた通り、math.sqrt を使わずに「2乗の比較」を行うことが、正確な判定を行うための定石です。

  ソースコード

import sys

def solve():
    # 競技プログラミングにおける高速な入力読み込み
    # 全ての入力を一度に読み込み、空白で分割してリスト化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 全ての文字列を整数に一括変換します
    # map(int, ...) は非常に高速です
    data = list(map(int, input_data))
    
    # 最初の4つの値（N, XA, YA, R）を取得します
    N = data[0]
    XA = data[1]
    YA = data[2]
    R = data[3]
    
    # ユークリッド距離の公式 √(dx^2 + dy^2) <= R を、
    # 計算速度と精度のために両辺を2乗した dx^2 + dy^2 <= R^2 で判定します
    R_sq = R * R
    total_satisfaction = 0
    
    # 各花火の情報はインデックス4から3つずつ並んでいます
    # (Xi, Yi, Pi)
    for i in range(N):
        idx = 4 + 3 * i
        xi = data[idx]
        yi = data[idx + 1]
        pi = data[idx + 2]
        
        # 高橋君の座標からの相対距離の2乗を計算
        dx = xi - XA
        dy = yi - YA
        dist_sq = dx * dx + dy * dy
        
        # 距離の2乗が R^2 以下であれば観覧可能
        if dist_sq <= R_sq:
            total_satisfaction += pi
            
    # 結果を出力します
    sys.stdout.write(str(total_satisfaction) + '\n')

if __name__ == '__main__':
    solve()

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