概要

\(N\) 人の学生の中から、全科目で最低基準点を満たす「基準通過者」を選び、その中で成績合計が上位 \(K\) 人（同点者は全員含む）を求める問題です。

考察

この問題は大きく3つのステップに分解できます。

1. 基準通過者のフィルタリング: 各学生について、すべての科目で最低基準点 \(T_j\) 以上かどうかを判定する。
2. 合計点によるソート: 基準通過者を全科目の合計点で降順にソートする。
3. 上位 \(K\) 人の選出（同点考慮）: 第 \(K\) 位の合計点と同じ点数の学生も全員含める。

素朴なアプローチでも、\(N\) 人それぞれに対して \(M\) 科目を確認するだけなので \(O(NM)\) で済みます。\(N \leq 10^5\)、\(M \leq 10\) なので最大でも \(10^6\) 程度の計算量であり、特別な工夫なしでも十分高速です。

同点処理が唯一の注意点です。例えば基準通過者が10人いて \(K = 3\) のとき、合計点の降順ソートで3位と4位が同点であれば、4位の学生も受給者に含めます。具体的には、\(K\) 番目の学生の合計点を「ボーダーライン（閾値）」として、それ以上の合計点を持つ基準通過者を全員選べばよいです。

アルゴリズム

1. 入力を読み込み、最低基準点の配列 \(T\) を取得する。
2. 各学生 \(i\)（\(1 \leq i \leq N\)）について：
   • すべての科目 \(j\) で \(S_{i,j} \geq T_j\) を満たすか判定する。
   • 満たす場合、合計点 \(\text{total} = \sum_{j} S_{i,j}\) と学生番号 \(i\) のペアをリストに追加する。
3. 基準通過者が0人なら何も出力せず終了。
4. リストを合計点の降順でソートする。
5. 基準通過者が \(K\) 人以下なら全員を受給者とする。
6. \(K\) 人より多い場合、ソート後の \(K\) 番目（0-indexed で \(K-1\) 番目）の合計点を閾値 \(\text{threshold}\) とし、合計点が \(\text{threshold}\) 以上の学生を全員選出する。
7. 受給者の学生番号を昇順にソートして出力する。

具体例: \(N=5\), \(M=2\), \(K=2\), \(T=[50, 50]\) で、基準通過者の合計点が \((300, 250, 250, 200)\) の場合。\(K=2\) 番目の合計点は \(250\)。合計点 \(250\) 以上の学生は3人いるので、3人全員が受給者になります。

計算量

• 時間計算量: \(O(NM + N \log N)\)
  • 各学生の基準判定と合計点計算に \(O(NM)\)
  • ソートに \(O(N \log N)\)（最悪全員が基準通過者の場合）
• 空間計算量: \(O(NM)\)
  • 入力データと基準通過者リストの保持

実装のポイント

• 高速な入力: sys.stdin.read() で一括読み込みし、split() で分割することで、input() を繰り返すより高速になります（\(N\) が大きい場合に有効）。

• 閾値による選出: ソート後に \(K\) 番目の値を閾値として保持し、リスト内包表記で一括フィルタリングすることで、同点処理をシンプルに実装できます。

• 出力順序: 問題は「学生番号の昇順」で出力を要求しているため、受給者リストを最後にもう一度ソートすることを忘れないようにしましょう。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    T = [int(input_data[idx + j]) for j in range(M)]
    idx += M
    
    passed = []
    for i in range(1, N + 1):
        scores = [int(input_data[idx + j]) for j in range(M)]
        idx += M
        if all(scores[j] >= T[j] for j in range(M)):
            total = sum(scores)
            passed.append((total, i))
    
    if not passed:
        return
    
    passed.sort(key=lambda x: -x[0])
    
    if len(passed) <= K:
        recipients = [p[1] for p in passed]
    else:
        threshold = passed[K - 1][0]
        recipients = [p[1] for p in passed if p[0] >= threshold]
    
    recipients.sort()
    print('\n'.join(map(str, recipients)))

main()

この解説は claude4.6opus-thinking によって生成されました。