概要

優先度が高い参加者から順に、ペア候補の中で番号が最も小さい未ペアの相手を選んでペアを組むシミュレーションを行い、参加者1（青木君）のペア相手を求める問題です。

考察

問題の本質

この問題は、明確なルール（貪欲法）に基づいてペアリングをシミュレーションする問題です。

1. 優先度が高い人から順に処理する: まず全参加者を優先度 \(R_i\) の降順にソートし、その順番で処理します。
2. 各参加者は、候補の中で番号が最小の未ペア相手を選ぶ: ある参加者 \(x\) の番になったとき、\(x\) の隣接リスト（ペア候補）の中から、まだペアになっていない参加者のうち番号が最小の人を選びます。

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

素朴に各参加者の隣接リストを毎回全探索すると、最悪の場合隣接リストの長さの合計 \(O(M)\) を何度も走査することになり、全体で \(O(N \times M)\) に近い計算量になりかねません。

解決策

隣接リストをソート済みデータ構造（SortedList）で管理すれば、番号が小さい順にイテレーションでき、最初に見つかった未ペアの候補がすぐに答えになります。さらに、参加者1がペアになった時点で即座に処理を打ち切ることで、無駄な計算を省きます。

実際には各参加者は高々1回しかペアリングの主体にならず、各辺も定数回しか参照されないため、全体の走査量はそこまで大きくなりません。

アルゴリズム

1. 入力の読み込み: 参加者数 \(N\)、ペア候補数 \(M\)、各参加者の優先度 \(R_i\)、ペア候補 \((U_j, V_j)\) を読み込む。
2. 隣接リストの構築: 各参加者について、ペア候補の相手を SortedList（常にソートされたリスト）で管理する。
3. 優先度降順に参加者をソート: 優先度 \(R_i\) が大きい順に参加者の番号を並べた配列 order を作る。
4. シミュレーション:
   • order の先頭から参加者 \(x\) を取り出す。
   • \(x\) が既にペア済みならスキップ。
   • \(x\) の隣接リスト（SortedList）を小さい番号から走査し、最初に見つかった未ペアの参加者 \(y\) とペアにする。
   • \(x\) または \(y\) が参加者1なら、相手の番号を記録して終了。
5. 結果を出力する。

具体例

\(N=4, M=3\), \(R = [3, 10, 1, 5]\)（参加者1〜4）、候補が \((1,2), (1,3), (3,4)\) の場合：

• 優先度降順: 参加者2（\(R=10\)）→ 参加者4（\(R=5\)）→ 参加者1（\(R=3\)）→ 参加者3（\(R=1\)）
• 参加者2の候補: \(\{1\}\) → 参加者1とペア
• 答えは 2（参加者1の相手は参加者2）

計算量

• 時間計算量: \(O(N \log N + M \log N)\)
  • 参加者のソートに \(O(N \log N)\)
  • 隣接リスト（SortedList）への挿入が全体で \(O(M \log N)\)
  • シミュレーション部分は各辺が高々定数回参照されるため \(O(M)\)（参加者1のペアが決まった時点で早期終了もあり得る）
• 空間計算量: \(O(N + M)\)（隣接リストとソート用配列）

実装のポイント

• SortedList の活用: Python の sortedcontainers.SortedList を使うことで、隣接リストを常にソート済みに保ち、番号が最小の未ペア候補を効率よく見つけられる。

• 早期終了: 青木君（参加者1）がペアになった時点で即座にループを抜けることで、不要な計算を回避している。

• paired 配列: 各参加者がペア済みかどうかを \(O(1)\) で判定するためのフラグ配列を用意する。

  ソースコード

import sys
from sortedcontainers import SortedList

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    R = [0] * (N + 1)
    for i in range(1, N + 1):
        R[i] = int(input_data[idx]); idx += 1
    
    # adjacency list using SortedList for each node
    adj = [None] * (N + 1)
    for i in range(1, N + 1):
        adj[i] = SortedList()
    
    for j in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u].add(v)
        adj[v].add(u)
    
    # Sort participants by priority descending
    # We need to process in order of decreasing R[i]
    order = sorted(range(1, N + 1), key=lambda i: -R[i])
    
    paired = [False] * (N + 1)
    answer = -1
    
    # To efficiently get the next unpaired person with highest priority,
    # we just iterate through the sorted order and skip paired ones
    for x in order:
        if paired[x]:
            continue
        # Find the smallest-numbered unpaired candidate in adj[x]
        # adj[x] is a SortedList, so we iterate from smallest
        y = None
        for candidate in adj[x]:
            if not paired[candidate]:
                y = candidate
                break
        
        # Pair x and y
        paired[x] = True
        paired[y] = True
        
        if x == 1:
            answer = y
            break
        if y == 1:
            answer = x
            break
    
    print(answer)

if __name__ == '__main__':
    main()

---

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