概要

数直線上の \(N\) 台のスピーカーと、測定点 \(P\) が与えられます。測定点と同じ座標にあるスピーカーを除き、残りのスピーカーからの音の強さ \(\frac{V_i}{|X_i - P|}\) の総和を求める問題です。

考察

この問題は、指示された計算式をそのまま実装することで解くことができます。

各スピーカーについて、測定点 \(P\) との距離 \(|X_i - P|\) を計算します。この距離が \(0\) の場合（すなわち \(X_i = P\) の場合）、ゼロ除算が発生してしまうため計算から除外します。距離が \(0\) でない場合のみ、\(\frac{V_i}{|X_i - P|}\) を合計値に加算します。

特別な工夫や高度なアルゴリズムは不要で、\(N\) 台のスピーカーを順番に調べて計算する素朴なアプローチで十分制限時間内に解くことができます。ただし、Pythonを用いる場合は入出力が多くなると遅くなるため、sys.stdin.buffer.read().split() を用いて入力を一括で読み込む高速化を行うと安心です。

アルゴリズム

1. スピーカーの台数 \(N\) と測定点の座標 \(P\) を読み込みます。
2. 音の強さの合計を保持する変数 ans を 0.0 で初期化します。
3. 各スピーカー \(i\) について、以下の処理を繰り返します。
   • スピーカーの座標 \(X_i\) と出力 \(V_i\) を読み込みます。
   • 差分 \(d = X_i - P\) を計算します。
   • \(d > 0\) の場合、ans に \(\frac{V_i}{d}\) を加算します。
   • \(d < 0\) の場合、ans に \(\frac{V_i}{-d}\) を加算します。
   • \(d = 0\) の場合、何もしません。
4. ans を出力します。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\) （入力データを配列として保持するため）

実装のポイント

• 距離の計算において、abs(X - P) を使ってゼロ除算を避けることも可能ですが、X - P の正負で分岐することで無駄な計算を省き、同時に \(X_i = P\) の場合を自然にスキップできます。

• 割り算を行う際、Pythonでは / 演算子を使って浮動小数点数として計算する必要があります。// 演算子（整数除算）を使うと正しい結果が得られません。

• 合計値の初期化を 0.0 とすることで、計算過程で暗黙的に浮動小数点数として扱われるようにしています。

  ソースコード

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    N = int(data[0])
    P = int(data[1])
    ans = 0.0
    idx = 2
    for _ in range(N):
        X = int(data[idx])
        V = int(data[idx + 1])
        dist = X - P
        if dist > 0:
            ans += V / dist
        elif dist < 0:
            ans += V / (-dist)
        idx += 2
    print(ans)

if __name__ == "__main__":
    solve()

この解説は or-glm-5.2-high によって生成されました。