概要

\(N\) 人の学生の中から、全科目で最低基準点を満たした「基準通過者」を抽出し、その中で合計点が高い上位 \(K\) 人（および \(K\) 位と同点の人）を特定する問題です。

考察

この問題を解くためには、以下の3つのステップを順番に処理していく必要があります。

1. 基準通過者のフィルタリング 各学生について、すべての科目 \(j\) で \(S_{i,j} \geq T_j\) を満たしているかを確認します。一人でも基準を下回る科目があれば、その学生は選考対象外となります。この際、後のランキングのために「合計点」と「学生番号」をセットで保存しておきます。
2. 合計点によるランキング 基準を通過した学生たちを、合計点の高い順（降順）に並べ替えます。
3. 受給者の確定と同点者の扱い 問題文の「第 \(K\) 位の合計成績と同点の学生は全員受給者とする」という条件に注意が必要です。
   • 基準通過者が \(K\) 人以下の場合は、全員が受給者となります。
   • 基準通過者が \(K\) 人より多い場合は、まず降順に並んだリストの \(K\) 番目の人のスコア（境界値）を確認します。そして、その境界値以上のスコアを持つ学生をすべて受給者として抽出します。

最後に、受給者の学生番号を昇順（番号の小さい順）に並べ替えて出力します。

アルゴリズム

1. 各科目の最低基準点 \(T_1, \dots, T_M\) を配列に格納します。
2. 各学生 \(i = 1, \dots, N\) について以下を行います：
   • 各科目の成績 \(S_{i,j}\) を読み込み、合計点 total_score を計算します。
   • すべての \(j\) について \(S_{i,j} \geq T_j\) であるか判定します。
   • 条件を満たす場合のみ、リスト passers に (total_score, i) を追加します。
3. passers を total_score の降順でソートします。
4. 受給者のリスト result_ids を作成します：
   • passers の要素数が \(K\) 以下なら、全員の学生番号を追加します。
   • \(K\) より多いなら、passers[K-1]（上位 \(K\) 番目）の合計点を threshold とし、合計点が threshold 以上の学生全員の番号を追加します。
5. result_ids を昇順にソートし、1行ずつ出力します。

計算量

• 時間計算量: \(O(NM + N \log N)\)
  • 全学生の成績チェックに \(O(NM)\) かかります。
  • 基準通過者のソートに最大 \(O(N \log N)\) かかります。
  • \(N=10^5, M=10\) であるため、全体で約 \(10^6\) 回程度の操作となり、制限時間内に十分収まります。
• 空間計算量: \(O(NM)\) または \(O(N)\)
  • 入力データを保持するのに \(O(NM)\)、通過者を管理するリストに \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が最大 \(10^5\) と大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() などで一括で入力を読み込む方が実行時間を短縮できます。

• ソートのキー: 合計点の降順でソートする際、Pythonの sort(key=..., reverse=True) を活用すると簡潔に記述できます。

• 最終出力の順序: 成績順に選んだ後、出力する前には「学生番号」で再度ソートし直す必要がある点に注意してください。”`

  ソースコード

import sys

def solve():
    # Use sys.stdin.read().split() to read all input tokens at once for speed.
    # This approach is generally more efficient for large inputs in Python.
    try:
        input_data = sys.stdin.read().split()
        if not input_data:
            return
        # Convert all tokens to integers.
        data = list(map(int, input_data))
    except (EOFError, ValueError):
        return

    # Basic parameters: N (number of students), M (number of subjects), K (recipient limit).
    if len(data) < 3:
        return
    N, M, K = data[0], data[1], data[2]
    
    # Minimum criteria points for each of the M subjects.
    if len(data) < 3 + M:
        return
    T = data[3 : 3 + M]
    
    passers = []
    # Student data starts from index 3 + M.
    # Each student has exactly M scores in the input.
    current_idx = 3 + M
    
    for i in range(1, N + 1):
        # Ensure we have enough data to read M scores for the student.
        if current_idx + M > len(data):
            break
            
        is_ok = True
        total_score = 0
        # Check if the student meets the minimum criterion for every subject.
        for j in range(M):
            score = data[current_idx + j]
            if score < T[j]:
                is_ok = False
            total_score += score
        
        # If the student meets all criteria, they are added to the list of "criteria passers".
        if is_ok:
            passers.append((total_score, i))
        
        # Move the index to the next student's data.
        current_idx += M
        
    # If no students passed the criteria, there are no recipients.
    if not passers:
        return
        
    # Sort the passers by their total score in descending order.
    # Python's sort is stable, which is helpful but not strictly required here.
    passers.sort(key=lambda x: x[0], reverse=True)
    
    # Determine the recipients based on the selection criteria.
    if len(passers) <= K:
        # If there are K or fewer passers, everyone who passed is a recipient.
        result_ids = [p[1] for p in passers]
    else:
        # If there are more than K passers, identify the score of the K-th person.
        # Since passers is 0-indexed, the K-th person is at index K-1.
        threshold_score = passers[K-1][0]
        # All passers with a total score greater than or equal to the K-th score are recipients.
        result_ids = [p[1] for p in passers if p[0] >= threshold_score]
        
    # The problem requires the student IDs of recipients to be output in ascending order.
    result_ids.sort()
    
    # Output the student IDs, one per line.
    if result_ids:
        sys.stdout.write('\n'.join(map(str, result_ids)) + '\n')

if __name__ == '__main__':
    solve()

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