概要

高橋君と青木君それぞれの位置から最も近い郵便局を見つけ、登録後の利用者数の合計を求める問題です。

考察

重要な気づき

1. 最寄りの郵便局を効率的に見つける必要がある: 郵便局が最大 \(2 \times 10^5\) 個あるため、各人に対して全ての郵便局との距離を計算する素朴な方法 \(O(N)\) でも間に合いますが、二分探索を使えば \(O(\log N)\) で見つけられます。

2. 同じ郵便局に登録するケースに注意: 二人が同じ郵便局に登録した場合、その郵便局の登録者数は1回だけ数えます（ただし二人分の +2 を加えた後の値）。

3. 最も近い郵便局が複数ある場合のタイブレーク: 距離が同じ場合は座標が最も小さい方を選ぶというルールがあります。

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

全探索で \(O(N)\) でも今回は間に合いますが、郵便局の数がさらに多くなった場合や、クエリが複数回ある場合を考えると、より効率的な方法が必要です。

アルゴリズム

1. 郵便局を座標順にソートする

郵便局を座標の昇順に並び替えることで、二分探索が使えるようになります。

2. 二分探索で最寄りの郵便局を見つける

位置 \(pos\) に対して最寄りの郵便局を見つける手順：

1. bisect_left で \(pos\) が入るべき位置 \(idx\) を求める
2. \(idx = 0\) の場合：全ての郵便局が \(pos\) より右にあるので、最も左の郵便局（インデックス 0）が最寄り
3. \(idx = N\) の場合：全ての郵便局が \(pos\) より左にあるので、最も右の郵便局（インデックス \(N-1\)）が最寄り
4. それ以外：左隣 \(xs[idx-1]\) と右隣 \(xs[idx]\) の2つを比較
   • 左への距離 \(\leq\) 右への距離 なら左（座標が小さい方を優先）
   • そうでなければ右

具体例: 郵便局が座標 \([1, 5, 10]\) にあり、\(pos = 7\) の場合 - bisect_left で \(idx = 2\)（7は5と10の間） - 左への距離: \(7 - 5 = 2\) - 右への距離: \(10 - 7 = 3\) - \(2 < 3\) なので座標 5 の郵便局（インデックス 1）が最寄り

3. 結果を計算

• 二人が同じ郵便局に登録 → その郵便局の元の登録者数 \(+ 2\)
• 別の郵便局に登録 → (高橋君の郵便局の登録者数 \(+ 1\)) \(+\) (青木君の郵便局の登録者数 \(+ 1\))

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • 二分探索に \(O(\log N)\) × 2回
• 空間計算量: \(O(N)\)
  • 郵便局の情報を格納するリスト

実装のポイント

1. タイブレークの実装: 距離が等しい場合に座標が小さい方を選ぶには、条件を dist_left <= dist_right とすることで自然に実現できます（等号の位置がポイント）。

2. 境界条件の処理: bisect_left の結果が 0 または \(N\) の場合、配列の範囲外アクセスを避けるため、先に場合分けして処理します。

3. 同じ郵便局かどうかの判定: インデックスを比較することで簡単に判定できます。

   ソースコード

import bisect

def solve():
    N, P, Q = map(int, input().split())
    
    posts = []
    for _ in range(N):
        x, c = map(int, input().split())
        posts.append((x, c))
    
    # 座標でソート
    posts.sort()
    
    xs = [p[0] for p in posts]
    
    def find_nearest(pos):
        # posに最も近い郵便局を見つける
        # 複数ある場合は座標が最も小さいものを選ぶ
        idx = bisect.bisect_left(xs, pos)
        
        if idx == 0:
            return 0
        elif idx == N:
            return N - 1
        else:
            # xs[idx-1] < pos <= xs[idx] または xs[idx-1] <= pos < xs[idx]
            dist_left = pos - xs[idx - 1]
            dist_right = xs[idx] - pos
            
            if dist_left <= dist_right:
                return idx - 1
            else:
                return idx
    
    idx_p = find_nearest(P)
    idx_q = find_nearest(Q)
    
    if idx_p == idx_q:
        # 同じ郵便局に登録
        result = posts[idx_p][1] + 2
    else:
        # 別の郵便局に登録
        result = (posts[idx_p][1] + 1) + (posts[idx_q][1] + 1)
    
    print(result)

solve()

---

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