概要

一直線上に並ぶ全ブースに音声を届けるため、スピーカーの設置位置を最適に選んだ上で、鳴らす回数 \(K\) を最小化する問題。答え \(K\) に対する二分探索と、各 \(K\) における区間の交差判定で解く。

考察

重要な気づき：\(K\) を固定すると条件が区間制約になる

\(K\) 回鳴らすとき、ブース \(i\) に音声が届く条件は：

\[K \times (V - |X_i - P|) \geq D_i\]

これを変形すると：

\[|X_i - P| \leq V - \lceil D_i / K \rceil\]

\(r_i = V - \lceil D_i / K \rceil\) とおくと、\(P\) が満たすべき条件は：

\[X_i - r_i \leq P \leq X_i + r_i\]

つまり、各ブースが「\(P\) はこの範囲にいてほしい」という区間を定めます。全ブースの条件を同時に満たすには、全区間の共通部分が空でないことを確認すればよいのです。

素朴なアプローチの問題点

\(P\) を全通り試すと座標が最大 \(10^9\) なので間に合いません。また \(K\) も最大 \(10^{18}\) まであり得るため全探索は不可能です。

解決策：\(K\) に対する単調性

\(K\) が大きいほど \(\lceil D_i / K \rceil\) は小さくなり、\(r_i\) が大きくなるため区間が広がります。よって「\(K\) が feasible」という判定は単調（ある値以上で常にYes）であり、二分探索が適用できます。

アルゴリズム

1. 不可能判定: \(V = 0\) なら音が届かないので -1。\(K \to \infty\) のとき \(r_i = V - 1\) となるので、区間 \([X_i - (V-1),\, X_i + (V-1)]\) の共通部分が空なら -1。

2. 二分探索: \(K\) の範囲を \([1,\, \max(D_i)]\) として二分探索。

3. 判定関数 feasible(K):

   • 各ブースについて \(r_i = V - \lceil D_i / K \rceil\) を計算
   • \(r_i < 0\) なら即 False
   • 全区間 \([X_i - r_i,\, X_i + r_i]\) の交差を求め、空でなければ True
   • 交差の計算：左端の最大値 \(\leq\) 右端の最小値 かを判定

計算量

• 時間計算量: \(O(N \log(\max D_i))\)
  • 二分探索が \(O(\log(\max D_i))\) 回、各判定で \(O(N)\)
  • \(\max D_i \leq 10^{18}\) なので \(\log\) は約 \(60\) 回
• 空間計算量: \(O(N)\)

実装のポイント

• 天井関数の整数計算: \(\lceil D_i / K \rceil\) は (D_i + K - 1) // K で計算。

• 整数座標の保証: \(X_i\), \(V\), \(K\) がすべて整数なので \(r_i\) も整数。区間の端点も整数となり、\(lo \leq hi\) なら整数 \(P\) が必ず存在する。

• 上界の設定: 最悪ケースはブースが距離 \(V-1\) にあり毎回音量 \(1\) しか届かない場合で、\(K = \max(D_i)\) 回必要。これが安全な上界。

• オーバーフロー対策: \(D_i\) が最大 \(10^{18}\) なので、Python の任意精度整数がそのまま使える利点がある。

  ソースコード

import sys
from math import ceil

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    V = int(input_data[idx]); idx += 1
    
    booths = []
    for i in range(N):
        X = int(input_data[idx]); idx += 1
        D = int(input_data[idx]); idx += 1
        booths.append((X, D))
    
    # For a given K, we need to find an integer position P such that for all booths i:
    # K * max(V - |X_i - P|, 0) >= D_i
    # This means: V - |X_i - P| >= ceil(D_i / K)  (when ceil(D_i/K) > V, impossible)
    # => |X_i - P| <= V - ceil(D_i / K)
    # Let r_i = V - ceil(D_i / K). If r_i < 0 for any i, then K is not enough.
    # Otherwise, P must satisfy: X_i - r_i <= P <= X_i + r_i for all i.
    # So P must be in [max(X_i - r_i), min(X_i + r_i)] and there must be an integer in this range.
    
    def feasible(K):
        lo = -10**18
        hi = 10**18
        for X, D in booths:
            needed = (D + K - 1) // K  # ceil(D/K)
            r = V - needed
            if r < 0:
                return False
            lo = max(lo, X - r)
            hi = min(hi, X + r)
            if lo > hi:
                return False
        # Check if there's an integer in [lo, hi]
        # lo and hi are integers (since X, r are integers), so just check lo <= hi
        return lo <= hi
    
    # First check if it's possible at all. 
    # The maximum K we'd ever need: for each booth, we need K * max(V - |X_i - P|, 0) >= D_i.
    # The best case for a booth is when |X_i - P| = 0, giving K * V >= D_i, so K >= ceil(D_i / V).
    # But we also need all booths within distance < V from P.
    
    # Check feasibility: even with K = infinity, we need all booths reachable from some P.
    # With K->inf, ceil(D_i/K) -> 1 (for D_i >= 1), so r_i = V - 1.
    # We need intersection of [X_i - (V-1), X_i + (V-1)] to be non-empty.
    # Actually for K large enough, ceil(D_i/K) = 1 (when K >= D_i), r_i = V-1.
    # But we should also consider: if V = 0, then no sound reaches anywhere (unless D_i = 0, but D_i >= 1).
    
    if V == 0:
        print(-1)
        return
    
    # Check if there exists any P that can reach all booths (with enough K).
    # With K->infinity, we need r_i = V - 1 >= 0, which is true since V >= 1.
    # And intersection of [X_i - (V-1), X_i + (V-1)] must be non-empty.
    lo_check = -10**18
    hi_check = 10**18
    for X, D in booths:
        lo_check = max(lo_check, X - (V - 1))
        hi_check = min(hi_check, X + (V - 1))
    
    if lo_check > hi_check:
        print(-1)
        return
    
    # Binary search on K
    # Lower bound: 1
    # Upper bound: max(ceil(D_i / 1)) but that's just max(D_i). 
    # Actually we need tighter: upper bound is when P is optimal.
    # Safe upper bound: for each booth, worst case K * 1 >= D_i (if booth is at distance V-1), so K = max(D_i).
    
    max_D = max(D for _, D in booths)
    
    left, right = 1, max_D
    
    # Check if K=max_D works (it should if feasibility passed)
    if not feasible(right):
        # Shouldn't happen, but just in case
        print(-1)
        return
    
    while left < right:
        mid = (left + right) // 2
        if feasible(mid):
            right = mid
        else:
            left = mid + 1
    
    print(left)

solve()

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