概要

直線上に並ぶ \(N\) 個のブースすべてに、スピーカーから必要な音量を届けるための「最小のスピーカー作動回数 \(K\)」を求める問題です。スピーカーの位置 \(P\) を最適に選ぶことで、作動回数 \(K\) を最小化します。

考察

1. 問題の言い換え（判定問題への帰着）

「最小の回数 \(K\) を求める」という問題を直接解くのは難しいですが、「スピーカーを \(K\) 回鳴らすとき、すべてのブースに十分な音量を届けられる設置位置 \(P\) が存在するか？」という判定問題を考えます。

作動回数 \(K\) を増やすほど、各ブースに届く音量が増えるため、条件を満たしやすくなります。この単調性（ある \(K\) で達成可能なら、それより大きい回数でも必ず達成可能であるという性質）を利用して、二分探索で最小の \(K\) を求めることができます。

2. \(K\) を固定したときの判定方法

作動回数 \(K\) を固定したとき、各ブース \(i\)（位置 \(X_i\), 閾値 \(D_i\)）について考えます。 ブース \(i\) に届く合計音量が \(D_i\) 以上になるためには、1回あたりに必要な音量を \(C_i\) とすると、 $\(C_i = \lceil D_i / K \rceil\)\( （\)D_i / K$ の小数点以下切り上げ）以上の音量が届く必要があります。

スピーカーの位置を \(P\) としたとき、届く音量は \(\max(V - |X_i - P|, 0)\) なので、条件は以下のようになります。 $\(\max(V - |X_i - P|, 0) \ge C_i\)$

これを満たす \(P\) の範囲を求めます。 * \(C_i > V\) のとき：スピーカーをブースの真上に置いても最大音量 \(V\) にしかならず、\(C_i\) に届きません。したがって、この場合はどのような \(P\) でも条件を満たすことは不可能です。 * \(C_i \le V\) のとき： $\(V - |X_i - P| \ge C_i \iff |X_i - P| \le V - C_i\)\( 絶対値を外すと、スピーカーの位置 \)P\( が満たすべき範囲は次の区間になります。 \)\(X_i - V + C_i \le P \le X_i + V - C_i\)$

各ブース \(i\) について、スピーカーを置くべき区間 \([L_i, R_i]\) が求まります。 * \(L_i = X_i - V + C_i\) * \(R_i = X_i + V - C_i\)

3. すべてのブースを同時に満たす \(P\) の存在判定

すべてのブース \(i\)（\(1 \le i \le N\)）について同時に条件を満たす \(P\) が存在するためには、それぞれのブースから定まる区間 \([L_i, R_i]\) すべてに共通部分が存在する必要があります。

共通部分が存在するための必要十分条件は、「すべての区間の左端の最大値が、右端の最小値以下であること」です。 つまり、以下の不等式が成り立てば、条件を満たす整数 \(P\) が存在します。 $\(\max_{1 \le i \le N} L_i \le \min_{1 \le i \le N} R_i\)$

この判定は、すべてのブースを1巡走査することで \(O(N)\) で行えます。

---

アルゴリズム

1. 二分探索の範囲の設定: \(K\) の最小値を low = 1、最大値を high = 10^18（\(D_i\) の最大値）とします。
2. 実現可能性の事前チェック: \(K\) を十分に大きく（high に）しても条件を満たせない場合は、どのようにスピーカーを設置しても不可能です。この場合は -1 を出力して終了します。
3. 二分探索の実行: low と high の中央値 mid について、check(mid) を行います。
   • 条件を満たす場合：さらに小さい \(K\) で達成できる可能性があるので、high = mid - 1 として探索を続けます。
   • 条件を満たさない場合：より大きい \(K\) が必要なので、low = mid + 1 とします。
4. 答えの出力: 探索によって得られた最小の \(K\) を出力します。

---

計算量

• 時間計算量: \(O(N \log(\max D_i))\) 二分探索の判定回数は \(\log_2(10^{18}) \approx 60\) 回です。1回の判定（check 関数）では \(N\) 個のブースを走査するため \(O(N)\) かかります。したがって、全体の実行時間は十分に高速で、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(N)\) 各ブースの座標 \(X_i\) と閾値 \(D_i\) を保持するための配列のサイズに比例します。

---

実装のポイント

• 切り上げ除算の書き方: \(D_i / K\) の切り上げ（\(\lceil D_i / K \rceil\)）は、整数同士の演算を用いて (D[i] + K - 1) / K と書くことができます。

• オーバーフローへの対策: \(D_i\) や \(K\) は最大で \(10^{18}\) に達するため、C++では long long 型を使用する必要があります。また、区間の端点 \(L_i, R_i\) を計算する際、一時的に非常に大きな値（または負の大きな値）になることがあるため、初期値として十分に大きな値（4e18 など）を設定しています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long V;
    if (!(cin >> N >> V)) return 0;

    vector<long long> X(N), D(N);
    for (int i = 0; i < N; ++i) {
        cin >> X[i] >> D[i];
    }

    // スピーカーを K 回鳴らしたときに条件を満たす設置位置 P が存在するか判定
    auto check = [&](long long K) -> bool {
        long long max_L = -4e18;
        long long min_R = 4e18;
        for (int i = 0; i < N; ++i) {
            // C_i = ceil(D[i] / K)
            long long C_i = (D[i] + K - 1) / K;
            if (C_i > V) return false;
            long long L_i = X[i] - V + C_i;
            long long R_i = X[i] + V - C_i;
            max_L = max(max_L, L_i);
            min_R = min(min_R, R_i);
        }
        return max_L <= min_R;
    };

    long long low = 1, high = 1e18;
    // K をいくら大きくしても（C_i = 1 にしても）条件を満たせない場合は -1
    if (!check(high)) {
        cout << -1 << "\n";
        return 0;
    }

    // 二分探索で最小の K を求める
    long long ans = high;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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