概要

各学生の成績が与えられ、すべての科目で基準点以上を満たした学生の中から、成績の合計が高い順に \(K\) 人（同点含む）を選抜する問題。

考察

この問題では、まず「すべての科目で基準点以上」を満たす学生（基準通過者）だけを対象とします。これは各学生ごとに全科目をチェックすることで判定できます。

次に、基準通過者の合計点を計算し、高い順に並べ替えます。ただし、同点の場合は学生番号の昇順という条件があります。そのため、ソートキーを (-合計点, 学生番号) とすることで、自然に条件を満たせます。

さらに注意すべきは、上位 \(K\) 人を選ぶときに、\(K\) 番目の得点と同じ得点を持つ学生は全員選ばれるという点です。例えば、\(K=3\) で上位3人の得点が [100, 90, 90] なら、90点の人は全員選ばれます。そのため、\(K\) 番目の得点を取得し、それ以上の得点を持つ学生をすべて抽出する必要があります。

素朴な方法として、最初から全員をソートして上位 \(K\) 人を取るだけでは、同点処理がうまくいかない可能性があるため、得点比較を行う必要があります。

また、制約より \(M \leq 10\) なので、各学生の基準通過判定や合計点の計算は高速に行えます。

アルゴリズム

1. 各学生について、すべての科目で基準点以上か判定し、基準通過者をリストアップする。
2. 基準通過者について、全科目の合計点を計算し、(合計点, 学生番号) の形で保存。
3. このリストを以下のルールでソート：
   • 合計点の降順（高い順）
   • 合計点が同じなら学生番号の昇順
4. ソート後、上位 \(K\) 人のうち最も低い得点を取得。
5. その得点以上の学生をすべて選抜（同点含む）。
6. 選抜された学生番号を昇順に出力。

計算量

• 時間計算量: \(O(N \cdot M + N \log N)\)
  • 各学生の基準通過判定に \(O(M)\)、それが \(N\) 人分 → \(O(N \cdot M)\)
  • ソートに \(O(N \log N)\)
• 空間計算量: \(O(N + M)\)
  • 基準点配列 \(T\) と、基準通過者のリストに必要な領域

実装のポイント

• 同点処理をするために、\(K\) 番目の得点を明確に取得し、それ以上の得点を持つ学生を全員選ぶ必要がある。
• ソートキーを (-score, id) とすることで、得点降順・番号昇順を同時に実現できる。
• 入力を高速に読み込むことで、\(N\) が最大 \(10^5\) でも間に合うようにしている。

## ソースコード

```python
import sys

# 入力の読み込み
input = sys.stdin.read
data = input().split()

idx = 0
N = int(data[idx])
idx += 1
M = int(data[idx])
idx += 1
K = int(data[idx])
idx += 1

# 基準点の読み込み
T = list(map(int, data[idx:idx+M]))
idx += M

# 学生データの読み込み
students = []
for i in range(N):
    scores = list(map(int, data[idx:idx+M]))
    idx += M
    # 基準通過判定
    passed = all(scores[j] >= T[j] for j in range(M))
    if passed:
        total = sum(scores)
        students.append((total, i + 1))  # (合計点, 学生番号)

# 合計点の降順、学生番号の昇順でソート
students.sort(key=lambda x: (-x[0], x[1]))

# 上位K人の合計点を取得（K番目と同じ点数の人も含む）
if not students:
    exit()

# K番目の合計点を取得
k_th_score = students[min(K, len(students)) - 1][0]

# K番目と同じ点数以上の学生をすべて選ぶ
recipients = [student[1] for student in students if student[0] >= k_th_score]

# 昇順にソートして出力
recipients.sort()
for num in recipients:
    print(num)

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