概要

各スピーカーについて、測定点までの距離が \(0\) でなければ \(\frac{V_i}{|X_i-P|}\) を計算し、その総和を求めます。浮動小数点数の加算誤差を抑えるため、補償付き加算を利用します。

考察

\(i\) 番目のスピーカーが測定点に与える音の強さは

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

です。そのため、入力されたスピーカーを順番に調べて、この値を足していけばよいです。スピーカー同士の組み合わせを考えたり、座標順に並べ替えたりする必要はありません。

ただし、\(X_i=P\) の場合は距離が \(0\) になります。このスピーカーは問題文の指示どおり計算から除外しなければなりません。除外せずに割り算を行うと、ゼロ除算が発生します。

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

• \((X_1,V_1)=(1,4)\)
• \((X_2,V_2)=(3,10)\)
• \((X_3,V_3)=(7,8)\)

それぞれについて、

• 1台目: \(\frac{4}{|1-3|}=\frac{4}{2}=2\)
• 2台目: \(X_2=P\) なので除外
• 3台目: \(\frac{8}{|7-3|}=\frac{8}{4}=2\)

となるため、答えは \(2+2=4\) です。

浮動小数点数の誤差

答えには分数が含まれるため、実数として計算する必要があります。しかし、コンピュータの浮動小数点数では、多数の値を加算すると丸め誤差が蓄積することがあります。

そこで、この実装では補償付き加算（Kahan summation）を使用しています。通常の合計値 total に加えて、直前までの加算で失われた小さな誤差を compensation に保持します。次に加える値からその誤差を差し引くことで、単純な加算よりも精度の高い合計を得られます。

アルゴリズム

1. 合計 total を \(0\)、補償値 compensation を \(0\) で初期化する。
2. 各スピーカーについて、次を行う。
   1. 距離 \(d=|X_i-P|\) を求める。
   2. \(d=0\) なら、そのスピーカーを計算から除外する。
   3. そうでなければ、音の強さ \(\frac{V_i}{d}\) を補償付き加算で total に加える。
3. total を十分な小数桁数で出力する。

補償付き加算では、加えたい項を \(a\) として次のように更新します。

• \(y=a-\text{compensation}\)
• \(t=\text{total}+y\)
• \(\text{compensation}=(t-\text{total})-y\)
• \(\text{total}=t\)

すべてのスピーカーが \(X_i=P\) を満たす場合は、一度も加算されないため、そのまま \(0\) が出力されます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• abs(x - p) で測定点までの距離を計算します。

• 距離が \(0\) の場合は、割り算を行う前に continue で除外します。

• total と compensation を浮動小数点数として管理し、補償付き加算を行います。

• print(f"{total:.15f}") のように十分な小数桁数を出力することで、要求される誤差 \(10^{-4}\) 以下を満たしやすくします。

• 入力数が最大 \(2\times 10^5\) と多いため、sys.stdin.buffer.readline を使って高速に読み込みます。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    n, p = map(int, input().split())

    total = 0.0
    compensation = 0.0

    for _ in range(n):
        x, v = map(int, input().split())
        distance = abs(x - p)
        if distance == 0:
            continue

        value = v / distance - compensation
        new_total = total + value
        compensation = (new_total - total) - value
        total = new_total

    print(f"{total:.15f}")

if __name__ == "__main__":
    main()

---

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