概要

各奨学金ごとに「応募者の中で評価点が最大、同点なら応募者番号が最小」の人を選び、その番号を出力する問題です。応募者がいなければ \(0\) を出力します。

考察

この問題は「奨学金 \(i\) に紐づいた応募者リスト」から、条件に合う 最優先の1人 を決めるだけです。
つまり、各奨学金について応募者を順に見て「今までの最良」を更新していけば答えが出ます。

重要な観察は次の2点です。

• 受給者の決定ルールは「最大化（評価点）＋タイブレーク（番号最小）」なので、比較規則が明確であり、リストを全部見れば必ず決まる。
• 制約で \(\sum K_i \le 2 \times 10^5\) なので、全奨学金の応募者を合計で1回ずつ見るようにすれば十分高速に間に合う。

素朴に「各奨学金ごとにソートして一番を取る」などをすると、奨学金ごとに \(O(K_i \log K_i)\) がかかり、合計で \(O\!\left(\sum K_i \log K_i\right)\) と無駄が出ます（最大ケースでは余計に重くなりがち）。
しかし本問は「1位だけ分かればよい」ので、ソートせず 線形走査で最良を更新するのが最適です。

例：奨学金の応募者が [3, 5, 2]、評価点が \(P_3=80, P_5=90, P_2=90\) のとき
- 最大評価点は \(90\)（応募者 5 と 2 が同点） - 同点なら番号が小さい 2 が勝つ
→ 答えは 2
これは走査中に「評価点がより大きい or 同点で番号が小さい」なら更新するだけで求まります。

アルゴリズム

1. 応募者 \(j\) の評価点 \(P_j\) を配列に保存する（\(1\)-indexed で持つと番号と対応しやすい）。
2. 各奨学金について：
   • \(K_i=0\) なら 0 を出力。
   • そうでなければ、best（現在の最良応募者番号）と bestP（その評価点）を持ち、応募者リストを先頭から見ていく。
   • 応募者 \(c\) を見たとき、以下なら更新する：
     • \(P_c > bestP\)（評価点が高い）
     • または \(P_c = bestP\) かつ \(c < best\)（同点で番号が小さい）
3. 各奨学金の best を出力する。

この比較規則により「評価点最大、同点なら番号最小」がそのまま実現できます。

計算量

• 時間計算量: \(O\!\left(M + \sum_{i=1}^{N} K_i\right)\)
  （評価点の読み込みが \(O(M)\)、各応募者IDを合計1回ずつ処理して \(O(\sum K_i)\)）
• 空間計算量: \(O(M)\)
  （評価点配列 \(P\) を保持）

実装のポイント

• 入力サイズが大きいので、sys.stdin.buffer.read() でまとめて読み、split()→map(int, ...) で高速化しています。

• 応募者番号は \(1 \sim M\) なので、評価点配列は P[M+1] を用意して P[c] で即参照できるようにします。

• タイブレーク（同点時の番号比較）を忘れると WA になるので、更新条件を
  pc > bestP or (pc == bestP and c < best)
  の形で正確に書くのが重要です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    P = [0] * (M + 1)
    for j in range(1, M + 1):
        P[j] = next(it)

    out_lines = []
    for _ in range(N):
        k = next(it)
        if k == 0:
            out_lines.append("0")
            continue
        best = 0
        bestP = -1
        for _ in range(k):
            c = next(it)
            pc = P[c]
            if pc > bestP or (pc == bestP and c < best):
                bestP = pc
                best = c
        out_lines.append(str(best))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。