概要

ダンスパーティーで優先度が高い参加者から順に、ペア候補の中から番号が最小の相手を選んでペアを組むルールにおいて、参加者1のペア相手を求める問題です。

考察

問題のルールをそのままシミュレーションする場合、優先度の高い参加者から順に処理する必要があります。各参加者について、ペア候補（グラフの隣接リスト）を事前に番号順にソートしておくことで、手順3で「番号が最も小さい相手」を効率的に選べます。素朴に全ての候補を毎回チェックすると最悪 \(O(N^2)\) 時間かかりますが、隣接リストを事前にソートし、未ペアの相手だけを選ぶようにすることで効率化できます。

アルゴリズム

1. 入力を受け取り、グラフを隣接リストで表現します。各頂点の隣接リストは番号順にソートします。
2. 参加者を優先度の降順にソートします。これで優先度が高い順に処理できます。
3. 各参加者について、未ペア状態であれば、その参加者の隣接リストを順に見て、最初に見つかった未ペアの相手とペアを組みます。
4. 全てのペアが決まった後、参加者1のペア相手を出力します。

計算量

• 時間計算量: \(O(N \log N + M \log N)\)
  • 優先度でのソートに \(O(N \log N)\)
  • グラフの各隣接リストのソートに合計 \(O(M \log N)\)（各頂点の次数を \(d_i\) とすると \(\sum d_i \log d_i \leq M \log N\)）
  • ペア決めの処理は各辺を高々1回チェックするので \(O(M)\)
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リストの保存に \(O(M)\)
  • 各種フラグや配列に \(O(N)\)

実装のポイント

• グラフは defaultdict(list) で表現し、各頂点の隣接リストを番号順にソートします。

• 優先度の降順で参加者を処理するため、(優先度, 参加者番号) のリストを作成しソートします。

• paired 配列でペア済みかを管理し、未ペアの参加者だけを相手として選びます。

• 参加者1のペアは partner[1] で直接取得できます。

  ソースコード

import sys
from collections import defaultdict

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    R = list(map(int, data[2:2+n]))
    edges = []
    index = 2 + n
    graph = defaultdict(list)
    for i in range(m):
        u = int(data[index]); v = int(data[index+1]); index += 2
        edges.append((u, v))
        graph[u].append(v)
        graph[v].append(u)
    
    for node in graph:
        graph[node].sort()
    
    priority_order = []
    for i in range(1, n+1):
        priority_order.append((R[i-1], i))
    priority_order.sort(reverse=True)
    
    paired = [False] * (n+1)
    partner = [0] * (n+1)
    
    for _, x in priority_order:
        if paired[x]:
            continue
        for y in graph[x]:
            if not paired[y]:
                partner[x] = y
                partner[y] = x
                paired[x] = True
                paired[y] = True
                break
                
    print(partner[1])

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。