概要

\(N\) 種類の奨学金に対してそれぞれ応募者が与えられるので、各奨学金において「評価点が最も高い人（同点なら番号が最も小さい人）」を特定する問題です。

考察

この問題で重要なのは、各奨学金に対して「誰が応募したか」と「その人の評価点はいくつか」を正確に紐付けて管理することです。

1. 評価点の管理

応募者の評価点 \(P_j\) は、応募者番号 \(j\) をインデックスとして配列（リスト）に格納しておくことで、いつでも \(O(1)\) で参照できるようになります。応募者番号は \(1\) から \(M\) までのため、サイズ \(M+1\) の配列を用意するのが効率的です。

2. 受給者の決定ルール

各奨学金において、応募者の中から一人を選ぶ条件は以下の通りです： - 原則として、評価点 \(P_j\) が最大である人を選ぶ。 - 評価点が最大となる人が複数いる場合は、その中で応募者番号 \(j\) が最小の人を選ぶ。

この比較処理は、各奨学金の応募者を一人ずつ確認しながら、「暫定のベスト応募者」を更新していくことで実現できます。

3. 計算量の見積もり

奨学金の数 \(N\) や応募者の総数 \(M\)、そして全奨学金の応募人数の合計 \(\sum K_i\) はすべて最大 \(2 \times 10^5\) です。 各応募者を 1 回ずつ確認して比較を行うため、全体の処理回数は \(\sum K_i\) に比例します。これは十分高速に動作し、制限時間内に間に合います。

アルゴリズム

1. 応募者の評価点 \(P_1, \ldots, P_M\) を配列 P に格納する。
2. 各奨学金 \(i = 1, \ldots, N\) について、以下の処理を行う：
   • 応募者数 \(K_i\) が \(0\) なら、0 を出力する。
   • \(K_i > 0\) なら、その奨学金の応募者 \(C_{i,k}\) を順番に確認する。
   • 変数 max_p（最大評価点）と best_c（その時の応募者番号）を用意し、より良い条件の応募者が現れるたびに更新する。
     • 「現在の応募者の点数 > max_p」または「現在の点数 == max_p かつ 現在の番号 < best_c」ならば更新。
   • 最終的な best_c を出力する。

計算量

• 時間計算量: \(O(N + M + \sum K_i)\)
  • 全ての評価点の読み込みに \(O(M)\)、全奨学金の走査に \(O(N)\)、そして全応募者の比較処理に合計 \(O(\sum K_i)\) かかります。制約はいずれも \(2 \times 10^5\) 程度であるため、全体で約 \(6 \times 10^5\) 回程度の操作となり、十分高速です。
• 空間計算量: \(O(M + \sum K_i)\)
  • 評価点を保存する配列に \(O(M)\)、入力を一括で読み込む場合に \(O(\sum K_i)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonでは入力データ量が多い場合、input() を繰り返すよりも sys.stdin.read().split() などで一括取得する方が大幅に高速化されます。

• 初期値の設定: 最大評価点を比較する際の初期値 max_p は、あり得る評価点の最小値（\(1\)）以下の値（例: \(-1\)）に設定しておくとスムーズに更新処理が行えます。

• 1-indexedの扱い: 応募者番号が \(1\) から始まるため、配列のサイズを \(M+1\) にしてインデックスを合わせると、ミスを防ぎやすくなります。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、イテレータを作成して高速にアクセスできるようにします。
    # この手法は、大規模な入力データを扱う競技プログラミングにおいてPythonでよく使われる高速化手法です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    
    # 奨学金の種類数 N と、応募者の人数 M を取得します。
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # 各応募者の評価点 P_1, P_2, ..., P_M を取得します。
    # 応募者番号は1から始まるため、1-indexedでリストに格納します。
    P = [0] * (M + 1)
    for i in range(1, M + 1):
        P[i] = int(next(it))
        
    results = []
    # 各奨学金について受給者を決定します。
    for _ in range(N):
        try:
            K = int(next(it))
        except StopIteration:
            break
            
        # 応募者がいない場合は 0 を出力リストに追加します。
        if K == 0:
            results.append("0")
            continue
        
        # 受給者を決定するための変数を初期化します。
        # best_c: 現在の最高評価点を持つ応募者の中で最も小さい番号
        # max_p: 現在の最高評価点
        best_c = -1
        max_p = -1
        
        # この奨学金に応募した K 人の応募者についてループを回します。
        for _ in range(K):
            c = int(next(it))
            p_c = P[c]
            
            # 選択ルール:
            # 1. 評価点が最も高い応募者を選ぶ。
            # 2. 評価点が同じ場合は、応募者番号が最も小さい応募者を選ぶ。
            if p_c > max_p:
                max_p = p_c
                best_c = c
            elif p_c == max_p:
                if c < best_c:
                    best_c = c
        
        # 決定した応募者番号を文字列として結果リストに追加します。
        results.append(str(best_c))
    
    # すべての結果を改行で区切って一度に出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。