概要

数直線上に配置されたスピーカーから、測定点 \(P\) に届く音の強さの総和を計算する問題です。

考察

問題文の指示通りに、各スピーカーについて音の強さを計算して足し合わせることを考えます。

\(i\) 番目のスピーカーについて、測定点 \(P\) に届く音の強さは次のように決まります。 - \(X_i \neq P\) のとき：\(\frac{V_i}{|X_i - P|}\) - \(X_i = P\) のとき：計算から除外（強さは \(0\) として扱う）

スピーカーの数 \(N\) は最大で \(2 \times 10^5\) です。各スピーカーに対する処理（距離の計算、除外判定、割り算、加算）は定数時間 \(O(1)\) で行えるため、\(N\) 個のスピーカーすべてを順番に調べる単純なループ処理を行えば、制限時間内に十分間に合います。

また、出力の許容誤差は \(10^{-4}\) 以下と指定されています。一般的なプログラミング言語の倍精度浮動小数点数（Python の float など）を用いれば、十分な精度で正しく計算することができます。

アルゴリズム

1. 答えを保持する変数 ans を 0.0 で初期化します。
2. 入力から \(N\) 個のスピーカーの情報 \((X_i, V_i)\) を順に取得します。
3. \(X_i \neq P\) である場合、ans に \(\frac{V_i}{|X_i - P|}\) を加算します。\(X_i = P\) の場合は何も行いません。
4. すべてのスピーカーの処理が終わったら、ans を十分な精度（少数点以下数桁〜十数桁）で出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個のスピーカーに対して、それぞれ \(O(1)\) の判定と計算を行うため、全体で \(O(N)\) となります。\(N \le 2 \times 10^5\) であり、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(N)\)
  • 入力データをまとめて取得するために \(O(N)\) のメモリを使用します。（1行ずつ処理する場合は \(O(1)\) に抑えることも可能です。）

実装のポイント

• ゼロ除算の回避: \(X_i = P\) の場合に \(|X_i - P| = 0\) となり、そのまま割り算を行うとエラー（ゼロ除算）が発生します。必ず if X_i != P: のように条件分岐を挟んで除外してください。

• 高速な入力受け取り: Python では input() を \(N\) 回呼び出すと実行時間が長くなることがあります。sys.stdin.read().split() を使うことで、大量の入力を高速に読み込むことができます。

  ソースコード

import sys


def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    it = iter(input_data)
    N = int(next(it))
    P = int(next(it))

    ans = 0.0
    for _ in range(N):
        x = int(next(it))
        v = int(next(it))
        if x != P:
            ans += v / abs(x - P)

    print(f"{ans:.12f}")


if __name__ == "__main__":
    main()

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