概要

数直線上の \(N\) 台のスピーカーのうち、測定点 \(P\) と異なる位置にあるスピーカーから測定点に届く音の強さ \(\frac{V_i}{|X_i - P|}\) の総和を求める問題です。

考察

問題文で与えられた計算式を忠実に実行することを考えます。

測定点 \(P\) にある各スピーカー \(i\)（\(1 \leq i \leq N\)）について、次の判定を行います。 - \(X_i = P\) の場合: 距離が \(0\) になり、音の強さが定義できないため無視します（加算しない）。 - \(X_i \neq P\) の場合: 距離は \(|X_i - P|\) となるため、音の強さ \(\frac{V_i}{|X_i - P|}\) を計算して合計に足します。

スピーカーの数 \(N\) は最大で \(2 \times 10^5\) です。1台ずつ順番に音の強さを計算して足し合わせる処理を行えば、制限時間内に余裕をもって間に合います。

また、解は小数になるため、浮動小数点数（double 型）を用いて計算する必要があります。

アルゴリズム

1. 合計値を保持する変数 ans を 0.0 で初期化します。
2. 1 番目から \(N\) 番目までのスピーカー情報を順番に読み込みます。
   • 座標 \(X_i\) と出力 \(V_i\) を受け取ります。
   • \(X_i = P\) ならば、何もしないで次のスピーカーの処理に移ります。
   • \(X_i \neq P\) ならば、距離 \(d = |X_i - P|\) を計算し、ans に \(\frac{V_i}{d}\) を加算します。
3. すべてのスピーカーの処理が終わったら、ans の値を十分な精度（例えば小数点以下15桁）で出力します。

計算量

• 時間計算量: \(O(N)\)
  • スピーカー1台あたりの計算は \(O(1)\) の定数時間で行えるため、\(N\) 台分の処理全体で \(O(N)\) となります。\(N \le 2 \times 10^5\) であるため、十分高速です。
• 空間計算量: \(O(1)\)
  • 入力を配列などに保持せず、受け取りながらその場で処理するため、追加で必要なメモリは定数個の変数のみとなります。

実装のポイント

• ゼロ除算の回避: \(X_i = P\) のときに距離が \(0\) となり、そのまま割るとプログラムが異常終了（ゼロ除算）するため、必ず条件分岐で除外します。

• 出力の精度: 問題文に「絶対誤差が \(10^{-4}\) 以下であれば正解」とあります。C++ の std::cout ではデフォルトで表示される桁数が少ない場合があるため、fixed と setprecision(15) を指定して十分な桁数を出力するようにします。

• 型の選択: 座標 \(X_i\) や \(P\) の値は絶対値が最大 \(10^9\) になるため、引き算の計算でオーバーフローしないよう、64ビット整数型（C++の long long）を使用すると安全です。

  ソースコード

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long p;
    if (!(cin >> n >> p)) return 0;

    double ans = 0.0;
    for (int i = 0; i < n; ++i) {
        long long x, v;
        cin >> x >> v;
        if (x == p) continue;
        long long dist = std::abs(x - p);
        ans += (double)v / dist;
    }

    cout << fixed << setprecision(15) << ans << "\n";

    return 0;
}

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