概要

高橋君と青木君がそれぞれ最寄りの郵便局に登録したとき、その2つの郵便局の利用者数の合計を求める問題です。ただし、同じ郵便局に登録した場合は重複して数えないように注意が必要です。

考察

この問題では、まず各人が最寄りの郵便局を選ぶ必要があります。単純には、すべての郵便局に対して距離を計算し、最小のものを選ぶという方法がありますが、郵便局の数 \(N\) が最大 \(2 \times 10^5\) あるため、毎回全探索すると時間計算量が \(O(N)\) となり、全体で \(O(N)\) かかってTLEになります。

そこで、郵便局を座標順にソートしておくことで、二分探索を用いて高速に最寄りの郵便局を見つけることができます。具体的には、bisect.bisect_left を使って、住んでいる座標に最も近い候補（左隣・右隣）を調べれば十分です。

さらに、同じ郵便局を選んだ場合、登録者数が2人増えるだけで、合計は1つの郵便局の登録者数として扱う必要がある点に注意します。つまり、異なる郵便局に登録した場合はそれぞれ1人ずつ増えた値を足し合わせ、同じ場合は1つの郵便局に2人追加された状態の値を出力します。

アルゴリズム

1. 郵便局の情報を \((X_i, C_i)\) として読み込み、座標 \(X_i\) の昇順にソートする。
2. 高橋君の座標 \(P\) と青木君の座標 \(Q\) それぞれについて、以下の手順で最寄りの郵便局を求める：
   • bisect_left を使い、ソート済みの座標リスト中で挿入位置を求める。
   • その位置の前後（最大3つ）の候補について、距離を比較し、最も近いものを選ぶ（距離が同じなら座標が小さい方）。
3. 2人が選んだ郵便局が同じかどうか判定する：
   • 同じなら、その郵便局の登録者数に2を加えた値を出力。
   • 異なるなら、両方の郵便局の登録者数にそれぞれ1を加えた値の和を出力。

計算量

• 時間計算量: \(O(N \log N)\)（ソートに dominate）
• 空間計算量: \(O(N)\)

実装のポイント

• 郵便局の情報を \((X_i, C_i)\) のペアでソートすること。

• bisect_left を使った探索によって、候補を最大3つに絞ることができる。

• 同じ郵便局に登録した場合の処理で、登録者数を2増やすだけであることに注意（同じオブジェクトなので二重にカウントしない）。

  ソースコード

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    P = int(data[1])
    Q = int(data[2])
    
    X = []
    C = []
    for i in range(N):
        x = int(data[3 + 2*i])
        c = int(data[4 + 2*i])
        X.append(x)
        C.append(c)
    
    # 座標でソート
    sorted_pairs = sorted(zip(X, C))
    X_sorted = [x for x, c in sorted_pairs]
    C_sorted = [c for x, c in sorted_pairs]
    
    # 最寄りの郵便局を探す関数
    def find_nearest(x):
        pos = bisect.bisect_left(X_sorted, x)
        candidates = []
        if pos < N:
            candidates.append((abs(X_sorted[pos] - x), X_sorted[pos], C_sorted[pos]))
        if pos > 0:
            candidates.append((abs(X_sorted[pos-1] - x), X_sorted[pos-1], C_sorted[pos-1]))
        if pos < N-1:
            candidates.append((abs(X_sorted[pos+1] - x), X_sorted[pos+1], C_sorted[pos+1]))
        
        # 距離でソートし、距離が同じなら座標が小さい方
        candidates.sort(key=lambda t: (t[0], t[1]))
        return candidates[0][1], candidates[0][2]
    
    Px, Pc = find_nearest(P)
    Qx, Qc = find_nearest(Q)
    
    if Px == Qx:
        total = Pc + Qc + 2 if Px != P or Qx != Q else Pc + Qc + 2  # どちらも新規登録なので+2
        # 実際には、元の登録者数 + 高橋君 + 青木君 の合計が Pc+2 や Qc+2 ではなく、
        # 登録後の人数は Pc+1 と Qc+1 （同じ局ならどちらも同じオブジェクト）
        # 同じ局なら、最終的な登録者数は元の人数 + 2 （高橋君と青木君）
        total = Pc + 2
    else:
        total = (Pc + 1) + (Qc + 1)
    
    print(total)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。