概要

各奨学金について、応募者の中から「評価点が最も高く、同点なら応募者番号が最も小さい」応募者を選ぶ問題です。

考察

問題の整理

この問題は、各奨学金ごとに独立して受給者を決定できます。奨学金同士は互いに影響しないため、各奨学金について以下の処理を行えばよいです：

1. その奨学金に応募した学生のリストを取得
2. リストが空なら \(0\) を出力
3. リストが空でなければ、「評価点最大」かつ「同点なら番号最小」の応募者を選ぶ

素朴なアプローチで問題ないか？

制約を確認すると： - 奨学金の数 \(N \leq 2 \times 10^5\) - 全奨学金の応募者数の合計 \(\sum_{i=1}^{N} K_i \leq 2 \times 10^5\)

この制約が重要です。各奨学金の応募者を全員見る方法でも、合計で見る応募者数は最大 \(2 \times 10^5\) 回に抑えられます。

つまり、各奨学金について応募者を線形に走査する素朴なアプローチで十分高速です。

アルゴリズム

1. 入力の読み込み: 応募者の評価点リスト \(P\) を配列に格納
2. 各奨学金について処理:
   • 応募者数 \(K_i\) と応募者リストを読み込む
   • \(K_i = 0\) なら、答えは \(0\)
   • \(K_i \geq 1\) なら、応募者リストを走査して最適な応募者を見つける
3. 最適な応募者の選び方:
   • 現在の最良候補（best）と最良スコア（best_score）を管理
   • 各応募者 \(c\) について：
     • \(c\) の評価点が best_score より大きい → 更新
     • \(c\) の評価点が best_score と同じで \(c\) が best より小さい → 更新

具体例

例えば、奨学金1に応募者 \(\{3, 1, 2\}\) がいて、評価点が \(P = [100, 150, 150]\) の場合： - 応募者3: 評価点 \(150\) - 応募者1: 評価点 \(100\) - 応募者2: 評価点 \(150\)

最高点は \(150\) で、応募者2と応募者3が該当。番号が小さい応募者2が受給者となります。

計算量

• 時間計算量: \(O(M + \sum_{i=1}^{N} K_i)\)
  • 評価点の読み込みに \(O(M)\)
  • 各奨学金の処理は応募者数に比例し、合計で \(O(\sum K_i)\)
• 空間計算量: \(O(M + \max K_i)\)
  • 評価点配列に \(O(M)\)
  • 各奨学金の応募者リストに最大 \(O(\max K_i)\)（順次処理するため）

実装のポイント

• 1-indexed と 0-indexed の変換: 応募者番号は \(1\) から始まる（1-indexed）が、配列 \(P\) は \(0\) から始まる（0-indexed）。応募者 \(c\) の評価点は P[c-1] でアクセスする

• 入力形式の注意: 各奨学金の行は「\(K_i\) \(C_{i,1}\) … \(C_{i,K_i}\)」の形式。\(K_i = 0\) の場合、その後に応募者番号がないことに注意

• 高速な入力: sys.stdin.readline を使うことで大量の入力を高速に処理

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    
    results = []
    for _ in range(N):
        line = list(map(int, input().split()))
        K = line[0]
        if K == 0:
            results.append(0)
        else:
            candidates = line[1:K+1]
            # Find the candidate with highest score, tie-break by smallest index
            best = None
            best_score = -1
            for c in candidates:
                score = P[c - 1]  # c is 1-indexed, P is 0-indexed
                if score > best_score or (score == best_score and c < best):
                    best_score = score
                    best = c
            results.append(best)
    
    print('\n'.join(map(str, results)))

if __name__ == '__main__':
    main()

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