概要

各スピーカーについて、測定点までの距離が \(0\) でなければ \(\frac{V_i}{|X_i-P|}\) を計算し、その値を合計します。

考察

各スピーカーから測定点に届く音の強さは、他のスピーカーとは独立に計算できます。したがって、すべてのスピーカーの組み合わせを調べたり、座標順に並べ替えたりする必要はありません。

\(i\) 番目のスピーカーと測定点との距離は

\(|X_i-P|\)

です。距離が \(0\) でなければ、そのスピーカーによる音の強さ

\(\frac{V_i}{|X_i-P|}\)

を合計に加えます。

一方、\(X_i=P\) の場合は分母が \(0\) になります。問題文ではこのスピーカーを計算から除外すると定められているため、割り算を行う前に距離が \(0\) かどうかを確認する必要があります。確認せずに割り算すると、ゼロ除算による実行時エラーになります。

例えば、測定点が \(P=3\) で、スピーカーが次のように置かれているとします。

• \((X,V)=(1,4)\)：強さは \(\frac{4}{|1-3|}=2\)
• \((X,V)=(3,10)\)：測定点と同じ座標なので除外
• \((X,V)=(7,8)\)：強さは \(\frac{8}{|7-3|}=2\)

したがって、合計は \(2+2=4\) です。

各スピーカーを一度ずつ調べればよいため、\(O(N)\) で十分です。スピーカー同士の組み合わせを調べる \(O(N^2)\) の処理は、\(N\) が最大 \(2\times 10^5\) なので間に合いません。

アルゴリズム

1. 合計値 total を \(0\) で初期化する。
2. \(N\) 台のスピーカーについて、次の処理を行う。
   1. 距離 distance を \(|X_i-P|\) として計算する。
   2. distance が \(0\) なら、そのスピーカーを無視する。
   3. そうでなければ、\(\frac{V_i}{\mathrm{distance}}\) を total に加える。
3. total を十分な小数桁数で出力する。

すべてのスピーカーが測定点と同じ座標にある場合も、total は初期値の \(0\) のままなので、そのまま正しく処理できます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)
  入力を sys.stdin.read().split() で一括して保持しているためです。合計を求める処理自体の追加空間は \(O(1)\) です。

実装のポイント

• abs(X - P) を使うことで、スピーカーが測定点の左右どちらにあっても正しい距離を計算できます。

• 距離が \(0\) の場合は、必ず割り算の前に除外します。

• 答えは整数とは限らないため、total は浮動小数点数として管理します。

• 誤差条件を満たすため、print(f"{total:.20f}") のように十分な桁数を出力します。

  ソースコード

def main():
    import sys
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx])
    idx += 1
    P = int(input_data[idx])
    idx += 1
    
    total = 0.0
    for _ in range(N):
        X = int(input_data[idx])
        idx += 1
        V = int(input_data[idx])
        idx += 1
        
        distance = abs(X - P)
        if distance != 0:
            total += V / distance
    
    print(f"{total:.20f}")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.6-sol-xhigh によって生成されました。