概要

参加者同士を特定のルールに従ってペアにするとき、参加者番号 \(1\) の人のペア相手を求める問題です。

考察

この問題では、各参加者に「優先度」が設定されており、優先度が高い人から順に自分のペアを選択します。選ぶ相手は、自分とのペア候補であり、かつまだ誰ともペアになっていない参加者の中から「番号が最も小さい人」になります。

この貪欲的な選択方式は一見シンプルですが、全員に対して毎回候補の中から最小番号を探すと、最悪ケースで \(O(N^2)\) となり、制約 \(N \leq 2 \times 10^5\) では間に合いません。

しかし、各参加者の「隣接リスト」を持っておけば、候補者を探す処理を効率化できます。具体的には、ある人 \(x\) の隣接リストを走査して、まだペアになっていない人の中から番号が最小のものを選ぶだけです。これにより、候補探索の部分も高速に行えます。

さらに、優先度が高い順に処理を行う必要があるため、「最大ヒープ」を使うのが適切です。Python では heapq は最小ヒープなので、優先度にマイナスをつけて管理することで擬似的に最大ヒープを実現できます。

最後に、ペアになったかどうかを記録する配列を持ち、すでにペアになっている人とはマッチングしないようにする必要があります。

アルゴリズム

1. 各参加者の優先度 \(R_i\) を読み込み、\((-R_i, i)\) の形で最大ヒープを構築。
2. 各ペア候補から隣接リストを作成（無向グラフ）。
3. ヒープから1人ずつ取り出し、その人がまだペアになっていなければ、隣接リストを見て未ペアの相手のうち番号最小の人とペアにする。
4. 全員ペアになるまでこれを繰り返す。
5. 最後に、参加者番号 \(1\) のペア相手を出力。

計算量

• 時間計算量: \(O(M + N \log N)\)
  • ヒープの構築と操作に \(O(N \log N)\)、隣接リストの走査全体で \(O(M)\)。
• 空間計算量: \(O(N + M)\)
  • 隣接リストと各種管理配列で \(O(N + M)\)。

実装のポイント

• 優先度の高い順に処理するために、heapq に \((-R_i, i)\) をプッシュする。

• 各ノードの隣接リストは list で持つことで、候補者の探索が効率的になる。

• ペア成立済みかどうかを管理するフラグ配列 paired を忘れずに更新すること。

• 青木君（番号 \(1\)）自身がペアになっていたら、そのパートナーを出力する。

  ソースコード

import heapq
import sys

input = sys.stdin.read

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    R = [0] * (N + 1)
    for i in range(1, N + 1):
        R[i] = int(data[i + 1])
    
    # 隣接リストの構築
    adj = [[] for _ in range(N + 1)]
    idx = N + 2
    for _ in range(M):
        u = int(data[idx])
        v = int(data[idx + 1])
        adj[u].append(v)
        adj[v].append(u)
        idx += 2
    
    # 優先度が高い順に処理するためのヒープ
    # (-R[i], i) で最大ヒープをシミュレート
    heap = []
    for i in range(1, N + 1):
        heapq.heappush(heap, (-R[i], i))
    
    # 各人のペア状態を管理
    paired = [False] * (N + 1)
    partner = [-1] * (N + 1)
    
    while heap:
        _, x = heapq.heappop(heap)
        if paired[x]:
            continue
        
        # x の隣接点の中で、まだペアが決まっていない最小番号を探す
        candidates = []
        for neighbor in adj[x]:
            if not paired[neighbor]:
                candidates.append(neighbor)
        
        if not candidates:
            continue  # ただし問題文よりこれは起こらない
        
        y = min(candidates)
        
        # x と y をペアにする
        paired[x] = True
        paired[y] = True
        partner[x] = y
        partner[y] = x
    
    print(partner[1])

if __name__ == "__main__":
    main()

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