概要

数直線上に設置された \(N\) 台のスピーカーについて、各スピーカーの音が測定点 \(P\) に届くときの強さ \(\frac{V_i}{|X_i - P|}\) の総和を計算する問題です。ただし、\(X_i = P\) となるスピーカーは計算から除外します。

考察

この問題は、各スピーカーごとに独立して音の強さを計算し、それらを足し合わせるだけのシンプルな問題です。特別なアルゴリズムやデータ構造は必要ありません。

重要なポイントは以下の2点です。

1. ゼロ除算の回避

測定点と同じ座標にスピーカーがある場合（\(X_i = P\)）、距離が \(0\) になり、\(\frac{V_i}{|X_i - P|}\) が計算できません。このようなスピーカーは計算から除外する必要があります。

具体的には、\(d = X_i - P\) を計算し、\(d = 0\) のときはそのスピーカーをスキップします。すべてのスピーカーが除外された場合でも、合計の初期値が \(0\) なので、そのまま \(0\) が出力されて正しい結果になります。

2. 絶対値の扱い

距離は \(|X_i - P|\) という絶対値です。\(d = X_i - P\) の符号に応じて、以下のように距離を求めます。

• \(d > 0\) のとき、距離は \(d\)
• \(d < 0\) のとき、距離は \(-d\)

たとえば \(P = 5\)、\(X_i = 3\)、\(V_i = 10\) の場合、\(d = 3 - 5 = -2\) なので距離は \(2\) となり、音の強さは \(\frac{10}{2} = 5\) になります。

アルゴリズム

各スピーカーについて順番に処理していきます。

1. 合計値 total を \(0\) で初期化します。
2. 各スピーカー \(i\) について、
   • \(d = X_i - P\) を計算します。
   • \(d \neq 0\) ならば、距離 \(|d|\) を求め、\(\frac{V_i}{|d|}\) を total に加算します。
   • \(d = 0\) ならば何もしません（スキップ）。
3. 最後に total を出力します。

これを愚直に \(N\) 台すべてに対して行うだけで答えが求まります。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)（入力を一度に読み込む場合。逐次処理すれば \(O(1)\)）

\(N \leq 2 \times 10^5\) なので、\(O(N)\) の処理で十分高速に間に合います。

実装のポイント

入力の高速化

\(N\) が最大 \(2 \times 10^5\) と比較的大きいため、input() を一行ずつ呼び出すと遅くなる可能性があります。sys.stdin.buffer.read() で入力を一括して読み込み、まとめて処理することで高速化しています。

絶対値の計算

Python では abs(d) で絶対値を求められますが、本コードでは d if d > 0 else -d という条件式を使って絶対値を計算しています。どちらの方法でも問題ありません。

誤差について

この問題は絶対誤差が \(10^{-4}\) 以下であれば正解となります。浮動小数点数（float）で計算すれば十分な精度が得られるため、特別な精度対策は不要です。Python の print はデフォルトで十分な桁数を出力してくれます。

ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    P = int(data[idx]); idx += 1
    total = 0.0
    for _ in range(N):
        X = int(data[idx]); idx += 1
        V = int(data[idx]); idx += 1
        d = X - P
        if d != 0:
            total += V / (d if d > 0 else -d)
    print(total)

main()

---

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