概要

各学生の全科目の成績が最低基準点以上であるかを確認し、条件を満たす学生の中から全科目の合計点が高い順に上位K人（同点の場合は全員）を選び、学生番号を昇順で出力する問題です。

考察

この問題では、まず各学生がすべての科目で最低基準点 \(T_j\) 以上であるかを確認する必要があります。すべての科目で基準を満たす学生だけが「基準通過者」となります。次に、基準通過者の中から合計点が高い順に選抜しますが、ポイントは以下の2点です：

1. 効率的なフィルタリング: 各学生について全科目（最大10科目）の成績をチェックするため、\(O(NM)\) で処理可能です。\(N\) は最大 \(10^5\)、\(M\) は最大10なので、\(10^6\) 回の比較で十分処理できます。

2. 同点処理: 合計点でソートした後、上位K人を選ぶ際に、第K位と同じ点数の学生が複数いる場合は全員を選ぶ必要があります。単純に上位K人を取るだけでは不十分で、同点の学生を適切に含める処理が重要です。

アルゴリズム

1. 入力読み込み: 学生数 \(N\)、科目数 \(M\)、選抜人数 \(K\)、各科目の基準点 \(T_j\)、各学生の成績を読み込みます。
2. 基準通過者の選出: 各学生について、全科目の成績が基準点以上かどうかをチェックします。条件を満たす学生は合計点と学生番号を記録します。
3. ソート: 基準通過者を合計点の降順（同点の場合は学生番号の昇順）でソートします。
4. 選抜: 上位K人を選びますが、第K位と同じ点数の学生がいる場合はそれらも含めます。具体的には、ソート後のリストの先頭から、合計点が第K位の点数以上である学生をすべて選びます。
5. 出力: 選ばれた学生番号を昇順で出力します。

計算量

• 時間計算量: \(O(NM + N \log N)\)
  • 基準通過者のチェックに \(O(NM)\)
  • ソートに \(O(N \log N)\)
  • \(M\) が最大10と小さいため、実質的には \(O(N \log N)\) が支配的です。
• 空間計算量: \(O(N)\)
  • 学生のデータを保持するためのリストが必要です。

実装のポイント

• 早期break: 基準点チェック中に1科目でも基準未満なら即座に処理を打ち切ることで、無駄な計算を省きます。

• 同点処理: ソート後、第K位の点数を閾値として、それ以上の点数を持つ学生をすべて選ぶことで、同点の学生を簡単に含められます。

• 効率的な入力処理: 大量の入力データを一括で読み込むことで、入出力のオーバーヘッドを減らしています。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    k = int(data[2])
    
    T = list(map(int, data[3:3+m]))
    
    students = []
    index = 3 + m
    for i in range(n):
        scores = list(map(int, data[index:index+m]))
        index += m
        students.append((i+1, scores))
    
    qualified = []
    for idx, scores in students:
        valid = True
        total = 0
        for j in range(m):
            if scores[j] < T[j]:
                valid = False
                break
            total += scores[j]
        
        if valid:
            qualified.append((total, idx))
    
    if not qualified:
        return
    
    qualified.sort(key=lambda x: (-x[0], x[1]))
    
    result = []
    if k >= len(qualified):
        result = [idx for _, idx in qualified]
    else:
        kth_score = qualified[k-1][0]
        for total, idx in qualified:
            if total >= kth_score:
                result.append(idx)
            else:
                break
    
    result.sort()
    for idx in result:
        print(idx)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。