概要

この問題は、一直線上に並ぶ複数のブースすべてに、スピーカーから必要な音量を届けるための最小の鳴らす回数 \(K\) を求める問題です。

スピーカーの設置位置 \(P\) を適切に選んだとき、条件を満たす最小の \(K\) を二分探索を用いて効率的に求めます。

---

考察

1. 素朴なアプローチとその限界

スピーカーの設置位置 \(P\) と鳴らす回数 \(K\) の両方を探索しようとすると、 \(P\) の候補は最大で \(10^9\) 通り、 \(K\) も最大で \(10^{18}\) に達するため、全探索（TLE）やシミュレーションは不可能です。

そこで、「\(K\) を固定したときに、条件を満たす設置位置 \(P\) が存在するか？」という判定問題に置き換えて考えます。

2. スピーカーを設置可能な前提条件

すべてのブースに音を届けるためには、スピーカーから各ブースへの距離が \(V\) 未満（すなわち \(V - 1\) 以下）でなければなりません。距離が \(V\) 以上離れると、何回鳴らしても届く音量は \(0\) になってしまうからです。

したがって、最も左にあるブースの座標 \(min\_X\) と、最も右にあるブースの座標 \(max\_X\) の距離が \(2V - 2\) より大きい場合、どのように \(P\) を選んでもすべてのブースに音を届けることは不可能です。 この場合は、探索を行う前に直ちに -1 を出力して終了できます。

\[max\_X - min\_X \ge 2V - 1 \implies \text{不可能 (-1)}\]

3. 回数 \(K\) を固定したときの設置位置 \(P\) の条件

鳴らす回数 \(K\) を固定したとき、ブース \(i\) に音声を届けるための条件は以下の通りです。

\[K \times \max(V - |X_i - P|, 0) \ge D_i\]

\(D_i \ge 1\) かつ \(K \ge 1\) より、 \(\max(V - |X_i - P|, 0) > 0\) である必要があります。よって、絶対値記号を外して整理すると以下のようになります。

\[V - |X_i - P| \ge \left\lceil \frac{D_i}{K} \right\rceil\]

\[|X_i - P| \le V - \left\lceil \frac{D_i}{K} \right\rceil\]

これをさらに \(P\) について解くと、ブース \(i\) の条件を満たすために \(P\) が存在しなければならない範囲が求まります。

\[X_i - V + \left\lceil \frac{D_i}{K} \right\rceil \le P \le X_i + V - \left\lceil \frac{D_i}{K} \right\rceil\]

すべてのブース \(i\) について、この \(P\) の範囲の共通部分（積集合）が存在すれば、その \(K\) は実現可能です。 具体的には、各ブースから得られる下限の最大値 \(max\_L\) と、上限の最小値 \(min\_R\) を求めたとき、以下が成り立てば条件を満たす \(P\) が存在します。

\[max\_L \le min\_R\]

4. 二分探索の適用

「回数 \(K\) で条件を満たす \(P\) が存在するか？」という判定問題は、 \(K\) が大きくなるほど条件が緩くなり（\(P\) の許容範囲が広くなり）、単調性（ある \(K\) で可能なら、それ以上の \(K\) でも必ず可能）を持ちます。 したがって、 \(K\) の値について二分探索を行うことができます。

---

アルゴリズム

1. 初期判定:

   • 全ブースの最小座標 \(min\_X\) と最大座標 \(max\_X\) を求めます。
   • \(max\_X - min\_X \ge 2V - 1\) であれば -1 を出力します。

2. 探索範囲の決定:

   • low (下限): スピーカーをブースの直上（距離0）に置いたとしても必要な最小回数。 $\(\text{low} = \max_{1 \le i \le N} \left\lceil \frac{D_i}{V} \right\rceil\)$
   • high (上限): 暫定的な位置 \(P = \lfloor (min\_X + max\_X) / 2 \rfloor\) に置いたときに、すべてのブースに音を届けるために必要な回数。

3. 二分探索:

   • mid = (low + high) // 2 とします。
   • mid 回で条件を満たす \(P\) が存在するかを \(O(N)\) で判定します。
     • 各ブース \(i\) について、 \(req_i = \lceil D_i / mid \rceil\) を計算します。
     • \(L_i = X_i - V + req_i\)
     • \(R_i = X_i + V - req_i\)
     • \(max\_L = \max(L_i)\) , \(min\_R = \min(R_i)\) を更新していきます。
     • 途中で \(max\_L > min\_R\) となった場合は、その時点で不可能と判定してループを抜けます。
   • 判定が「可能」なら、さらに小さい \(K\) を探すため high = mid - 1 とし、答えの候補を更新します。
   • 判定が「不可能」なら、より大きい \(K\) が必要なため low = mid + 1 とします。

---

計算量

• 時間計算量: \(O(N \log (\text{high} - \text{low}))\)

  • 二分探索の判定処理は、各ブースに対して \(O(1)\) の計算を \(N\) 回行うため、1回あたり \(O(N)\) です。
  • \(D_i \le 10^{18}\) より、探索範囲の幅は最大で \(10^{18}\) 程度です。二分探索のループ回数は \(\log_2(10^{18}) \approx 60\) 回となります。
  • したがって、全体の計算量は約 \(60 \times N\) となり、実行時間制限に十分間に合います。

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

  • 各ブースの座標と聴取閾値を保存するために \(O(N)\) のメモリを使用します。

---

実装のポイント

1. 切り上げ除算の整数計算

プログラミングにおいて、正の整数 \(A, B\) に対する切り上げ除算 \(\lceil A / B \rceil\) は、浮動小数点数を使わずに整数演算のみで以下のように計算できます。これにより、小数の精度問題を回避できます。

(A + B - 1) // B

2. 探索範囲の最適化

上限 high を一律で \(10^{18}\) のような極端に大きな値にしても正しく動作しますが、コード中のように「中央付近の座標 \(P\) に置いたと仮定したときの必要回数」を high の初期値とすることで、二分探索の範囲を狭め、実行時間をさらに短縮することができます。

ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    V = int(data[1])
    
    XD = []
    idx = 2
    for _ in range(N):
        XD.append((int(data[idx]), int(data[idx+1])))
        idx += 2
        
    min_X = XD[0][0]
    max_X = XD[0][0]
    for x, _ in XD:
        if x < min_X:
            min_X = x
        if x > max_X:
            max_X = x
            
    if max_X - min_X >= 2 * V - 1:
        print(-1)
        return

    # K の下限 (low) の計算
    low = 1
    for _, d in XD:
        val = (d + V - 1) // V
        if val > low:
            low = val
            
    # K の上限 (high) の計算
    # P を (min_X + max_X) // 2 に置いたときに必要な K を上限とする
    P = (min_X + max_X) // 2
    high = 1
    for x, d in XD:
        dist = abs(x - P)
        val = (d + V - dist - 1) // (V - dist)
        if val > high:
            high = val
            
    # 二分探索
    ans = high
    while low <= high:
        mid = (low + high) // 2
        possible = True
        max_L = -10**18
        min_R = 10**18
        for x, d in XD:
            req = (d + mid - 1) // mid
            L = x - V + req
            if L > max_L:
                max_L = L
            R = x + V - req
            if R < min_R:
                min_R = R
            if max_L > min_R:
                possible = False
                break
        if possible:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
            
    print(ans)

if __name__ == '__main__':
    solve()

---

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