概要

各学生が「全科目で最低点以上か」を判定して基準通過者を集め、通過者の中から合計点が高い順に上位 \(K\) 位（同点は全員）までの学生番号を昇順で出力する問題です。

考察

まず「基準通過者」の条件は 全科目で \(S_{i,j} \ge T_j\) なので、学生ごとに \(M\) 科目を見れば判定できます（\(M \le 10\) なので十分軽い）。

次に、受給者の決め方が少し注意点です：

• 基準通過者を合計点の降順に並べたとき
• 「上位 \(K\) 人」だが、第 \(K\) 位と同点の学生がいれば全員採用
  → つまり「合計点が第 \(K\) 位の合計点以上の通過者は全員採用」です。

素朴に「基準通過者を全部ソートして、先頭 \(K\) 人だけ取る」だと、同点処理を忘れて WA になります。
例：合計点が [100, 90, 80, 80, 70]、\(K=3\) のとき、第3位は80点で同点がいるので、採用は80点の2人を含めて 4人 になります。

この同点処理は、「第 \(K\) 位の合計点（境界値）を求め、その値以上を全員採用」とすると簡潔に処理できます。

アルゴリズム

1. 入力を読み込む。
2. 各学生 \(i\) について
   • 全科目で \(S_{i,j} \ge T_j\) かを判定する（1つでも下回れば失格）。
   • 同時に合計点 \(sum_i=\sum_{j=1}^{M} S_{i,j}\) を計算する。
   • 基準を満たす学生だけ (sum_i, i) を配列 qualified に入れる。
3. qualified の人数を \(Q\) とする。
   • \(Q=0\) なら何も出力しない。
   • \(Q \le K\) なら、基準通過者全員を採用（番号を昇順にして出力）。
   • \(Q > K\) なら、
     1. qualified を合計点の降順でソート
     2. 第 \(K\) 位（0-indexで K-1）の合計点 kth_sum を取得
     3. 合計点が kth_sum 以上の学生を全員集め、学生番号を昇順で出力

計算量

• 時間計算量:
  基準判定・合計計算が \(O(NM)\)、通過者数を \(Q\) としてソートが \(O(Q \log Q)\)
  よって全体で \(O(NM + Q \log Q)\)（\(M \le 10\) なので十分高速）
• 空間計算量: \(O(Q)\)（基準通過者の (合計点, 番号) を保持）

実装のポイント

• \(N \le 10^5\) なので、Pythonでは sys.stdin.buffer.read() でまとめて読み取ると安定して高速です。

• 同点処理は「第 \(K\) 位の合計点 kth_sum を求め、total >= kth_sum を全員採用」とすると漏れがありません。

• 出力は「学生番号の昇順」指定なので、採用者の番号だけ最後に sorted() してから改行区切りで出力します。

• 基準通過者が 0 人のときは何も出力しない仕様なので、早めに return します。

  ソースコード

import sys

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

    N = next(it)
    M = next(it)
    K = next(it)

    T = [next(it) for _ in range(M)]

    qualified = []
    for i in range(1, N + 1):
        total = 0
        ok = True
        for j in range(M):
            s = next(it)
            if s < T[j]:
                ok = False
            total += s
        if ok:
            qualified.append((total, i))

    qn = len(qualified)
    if qn == 0:
        return

    if qn <= K:
        ans = sorted(idx for _, idx in qualified)
    else:
        qualified.sort(key=lambda x: x[0], reverse=True)
        kth_sum = qualified[K - 1][0]
        ans = sorted(idx for total, idx in qualified if total >= kth_sum)

    sys.stdout.write("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

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