概要

数直線上の \(N\) 個の郵便局の中から、2人の住人（高橋君と青木君）がそれぞれ自分に最も近い郵便局を選びます。2人が登録した後の、対象となる郵便局の利用者数の合計を求める問題です。

考察

郵便局の数 \(N\) が最大 \(2 \times 10^5\) と大きいため、各個人について \(N\) 個の郵便局をすべて調べて距離を計算する（線形探索）と、全体で \(O(N)\) の時間がかかります。今回は 2 人だけなので線形探索でも間に合いますが、より効率的に「最も近い要素」を探すには、二分探索を利用するのが一般的です。

二分探索を行うためには、郵便局のデータが座標 \(X_i\) の昇順に並んでいる必要があります。

最寄りの郵便局の探し方

ある座標 \(pos\) に最も近い郵便局は、座標順にソートされたリストの中で以下のいずれかになります。 1. \(pos\) 以上の座標の中で最小のもの（bisect_left で見つかる位置 idx） 2. \(pos\) 未満の座標の中で最大のもの（idx - 1 の位置）

この 2 つの候補の距離を比較します。問題文に「距離が同じ場合は座標が小さい方を選ぶ」という条件があるため、距離が等しい場合は idx - 1 の方を選択するように実装します。

合計利用者数の計算

高橋君が選んだ郵便局のインデックスを t_idx、青木君が選んだものを a_idx とします。 - 2人が同じ郵便局を選んだ場合 (t_idx == a_idx): その郵便局の元の利用者数 \(C_{t\_idx}\) に、2人分の登録を加えて \(C_{t\_idx} + 2\) となります。 - 2人が異なる郵便局を選んだ場合 (t_idx != a_idx): それぞれの郵便局に1人ずつ登録されるため、\((C_{t\_idx} + 1) + (C_{a\_idx} + 1)\) となります。

アルゴリズム

1. 郵便局の情報を入力し、座標 \(X_i\) をキーとして昇順にソートします。
2. 二分探索（Pythonでは bisect モジュール）を用いて、高橋君の座標 \(P\) および青木君の座標 \(Q\) に最も近い郵便局のインデックスを特定します。
   • 座標リスト xs に対して bisect_left を使い、挿入位置 idx を得ます。
   • xs[idx] と xs[idx-1] のうち、より \(pos\) に近く、条件を満たす方を選びます。
3. 特定したインデックスに基づき、条件分岐を行って最終的な利用者数の合計を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 郵便局のソートに \(O(N \log N)\) かかります。
  • 二分探索は \(O(\log N)\) であり、2人分行っても \(O(\log N)\) です。
• 空間計算量: \(O(N)\)
  • 郵便局の情報を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 二分探索の境界: bisect_left が返すインデックスが 0（すべての郵便局が右側にある）や N（すべての郵便局が左側にある）になる場合に注意して処理を分ける必要があります。

• 高速な入出力: \(N\) が大きいため、Pythonでは sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 同じ郵便局の判定: インデックス（または座標）を比較することで、2人が同じ場所を選んだかどうかを正確に判定できます。

  ソースコード

import sys
import bisect

def solve():
    # 入力を一括で読み込み、スペースや改行で分割してリスト化します。
    # N=2*10^5 程度の入力であれば、この方法がPythonにおいて高速です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 郵便局の数, P: 高橋君の座標, Q: 青木君の座標
    N = int(input_data[0])
    P = int(input_data[1])
    Q = int(input_data[2])
    
    # 郵便局の情報 (座標 X, 利用者数 C) を格納します。
    offices = []
    for i in range(N):
        x = int(input_data[3 + 2 * i])
        c = int(input_data[4 + 2 * i])
        offices.append((x, c))
    
    # 座標順にソートすることで、二分探索を利用可能にします。
    offices.sort()
    
    # 二分探索用に座標のみのリストを作成します。
    xs = [o[0] for o in offices]
    
    def find_nearest_index(pos):
        """
        指定された座標 pos から最も近い郵便局のインデックスを返します。
        距離が同じ場合は、座標が小さい方を選択します。
        """
        # bisect_left は pos を挿入すべき位置（xs[idx] >= pos となる最小の idx）を返します。
        idx = bisect.bisect_left(xs, pos)
        
        # pos がすべての郵便局の座標より小さい場合
        if idx == 0:
            return 0
        # pos がすべての郵便局の座標より大きい場合
        if idx == N:
            return N - 1
        
        # 候補は xs[idx-1] と xs[idx] の2つです。
        dist_left = abs(pos - xs[idx - 1])
        dist_right = abs(xs[idx] - pos)
        
        # 最も近いものを選び、距離が同じなら座標が小さい方 (idx-1) を選びます。
        if dist_left <= dist_right:
            return idx - 1
        else:
            return idx
    
    # 高橋君と青木君がそれぞれ選ぶ郵便局のインデックスを求めます。
    t_idx = find_nearest_index(P)
    a_idx = find_nearest_index(Q)
    
    if t_idx == a_idx:
        # 二人が同じ郵便局に登録した場合
        # その郵便局の登録者数は元の人数に二人分（+2）を加えたものになります。
        print(offices[t_idx][1] + 2)
    else:
        # 二人が異なる郵便局に登録した場合
        # それぞれの郵便局の登録者数を1人ずつ増やした後の合計を求めます。
        print((offices[t_idx][1] + 1) + (offices[a_idx][1] + 1))

if __name__ == '__main__':
    solve()

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