概要

各奨学金ごとに応募者の中から、評価点が最も高く、さらに応募者番号が最も小さい人を選ぶ問題。

考察

この問題では、各奨学金ごとに応募者のうち「評価点の高い順、同じなら番号の小さい順」にソートし、最上位の人物を選べばよいです。

素朴な方法として、毎回該当する応募者をリストアップしてソートする方法がありますが、制約が非常に大きいため（\(N, M \sim 2 \times 10^5\)）、全体で \(\sum K_i \leq 2 \times 10^5\) もあるため、効率的な処理が必要です。

しかし、この問題ではオンラインジャッジでの高速化のために入力を高速に行う必要があり、また毎回のソートも定数時間に近いオーバーヘッドを持つ必要があります。Pythonの標準入力は遅いため、sys.stdin.read を使って一度に全て読み込む工夫が必要です。

幸い、各奨学金ごとの候補者数 \(K_i\) が比較的小さく、全体の合計も \(2 \times 10^5\) を超えないため、候補者を一旦リストアップしてソートしても十分間に合います。

アルゴリズム

1. まず、全応募者の評価点を配列 \(P\) に格納しておく（インデックスは応募者番号）。
2. 各奨学金について：
   • 応募者がいない場合（\(K_i = 0\)）は 0 を出力。
   • 応募者がいる場合：
     • 各応募者の評価点と番号のペア \((P[c], c)\) をリストに格納。
     • このリストを「評価点の降順 → 応募者番号の昇順」でソート。
     • 最初の要素が受給者となるので、その応募者番号を出力。

計算量

• 時間計算量: \(O(\sum K_i \log (\max K_i))\) （各奨学金ごとのソートにかかる時間）
• 空間計算量: \(O(M + \max K_i)\)

実装のポイント

• 入力が非常に多いので、sys.stdin.read を使い一度に読み込んで分割する。

• 応募者番号は1-indexedなので、評価点配列 \(P\) も1-indexedで持つ。

• ソートキーは (-score, id) のようにすることで、評価点の降順、IDの昇順になる。

• 結果は最後にまとめて出力すると高速になる（print('\n'.join(result))）。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    P = [0] * (M + 1)
    for j in range(1, M + 1):
        P[j] = int(data[idx])
        idx += 1

    result = []
    for _ in range(N):
        K = int(data[idx])
        idx += 1
        if K == 0:
            result.append('0')
            continue
        candidates = []
        for __ in range(K):
            c = int(data[idx])
            idx += 1
            candidates.append((P[c], c))
        # Sort by score descending, then by ID ascending
        candidates.sort(key=lambda x: (-x[0], x[1]))
        winner = candidates[0][1]
        result.append(str(winner))
    
    print('\n'.join(result))

if __name__ == "__main__":
    main()

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