概要

各スピーカーについて \(\frac{V_i}{|X_i - P|}\) を計算し、その総和を求める問題です。測定点と同じ座標にあるスピーカー（\(X_i = P\)）は除外して計算します。

考察

この問題は、複雑なアルゴリズムを必要とせず、問題文で定義された計算をそのまま実行するだけで解くことができます。

重要なポイントは以下の通りです。

1. 各スピーカーは独立に計算できる

\(i\) 番目のスピーカーが測定点に届ける音の強さは \(\frac{V_i}{|X_i - P|}\) であり、他のスピーカーとは無関係に計算できます。したがって、すべてのスピーカーについて順番に計算し、その値を足し合わせればよいだけです。

2. ゼロ除算の回避

\(X_i = P\) のとき、距離 \(|X_i - P|\) が \(0\) になってしまい、割り算ができません。この場合はそのスピーカーを計算から除外する必要があります。具体的には、X == P のときはスキップする処理を入れます。

例えば、測定点 \(P = 5\) で、スピーカーが \(X = 5\) にある場合、このスピーカーは無視します。

3. 絶対値の扱い

距離は \(|X_i - P|\) なので、\(X_i - P\) の符号にかかわらず正の値になります。たとえば \(X_i = 3, P = 5\) なら距離は \(|3 - 5| = 2\)、\(X_i = 8, P = 5\) なら距離は \(|8 - 5| = 3\) です。絶対値を取り忘れると距離が負になり、誤った結果になるので注意しましょう。

アルゴリズム

アルゴリズムは非常にシンプルです。

1. 合計値を格納する変数 sum を \(0\) で初期化する。
2. 各スピーカー \(i\) について以下を行う：
   • \(X_i = P\) ならスキップする。
   • そうでなければ、\(\frac{V_i}{|X_i - P|}\) を計算して sum に加える。
3. 最後に sum を出力する。

計算結果は実数（浮動小数点数）になるため、double 型で扱います。問題文で絶対誤差 \(10^{-4}\) 以下が許容されているので、double の精度で十分です。

計算量

• 時間計算量: \(O(N)\)（各スピーカーを一度ずつ処理するだけ）
• 空間計算量: \(O(1)\)（合計値を保持する変数のみで、入力を配列に保存する必要もない）

\(N \leq 2 \times 10^5\) なので、この計算量で余裕を持って間に合います。

実装のポイント

オーバーフローに注意

\(X_i\) と \(P\) はともに \(-10^9 \leq X_i, P \leq 10^9\) の範囲なので、\(X_i - P\) の絶対値は最大で \(2 \times 10^9\) になります。これは 32bit 整数（int）の範囲（約 \(2.1 \times 10^9\)）に近く、計算過程で危険なので、long long 型で扱うのが安全です。コードでは P, X, V をすべて long long で受け取っています。

割り算の型変換

整数同士で割り算すると小数点以下が切り捨てられてしまいます。必ず (double) にキャストしてから割り算を行いましょう。

sum += (double)V / (double)llabs(X-P);

このように分子・分母を double に変換することで、正しく実数の割り算が行われます。

出力の精度

絶対誤差 \(10^{-4}\) 以下が許容されていますが、余裕を持って小数点以下 \(10\) 桁程度まで出力しておけば安心です。コードでは printf("%.10f\n", sum); としています。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    long long P;
    scanf("%d %lld", &N, &P);
    double sum = 0.0;
    for(int i=0;i<N;i++){
        long long X, V;
        scanf("%lld %lld", &X, &V);
        if(X==P) continue;
        sum += (double)V / (double)llabs(X-P);
    }
    printf("%.10f\n", sum);
    return 0;
}

---

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