概要

各クラスについて、テストの点数が基準点 \(K\) 以上の生徒の人数を数えて出力する問題です。

考察

この問題は、各クラスごとに生徒の点数を確認し、条件を満たす人数をカウントするだけのシンプルな問題です。

重要な気づき

1. 各クラスは独立: クラス間で情報を共有する必要がなく、各クラスを順番に処理すればよい
2. 単純な条件判定: 各生徒について「点数 \(\geq K\) か？」を判定するだけ

素朴なアプローチで問題ないか？

この問題では、全生徒を1回ずつ確認するだけで十分です。制約を確認すると： - 全クラスの生徒数の合計 \(\sum_{i=1}^{N} M_i \leq 10^6\)

つまり、最大でも \(10^6\) 人の生徒を1回ずつ確認するだけなので、素朴なアプローチで十分間に合います。

具体例

入力例として以下を考えます：

3 60
3 55 70 80
2 60 59
4 100 50 60 70

• \(N = 3\)（クラス数）、\(K = 60\)（基準点）
• クラス1: 点数は 55, 70, 80 → 60点以上は 70, 80 の 2人
• クラス2: 点数は 60, 59 → 60点以上は 60 の 1人
• クラス3: 点数は 100, 50, 60, 70 → 60点以上は 100, 60, 70 の 3人

出力は 2, 1, 3 となります。

アルゴリズム

1. 1行目から \(N\)（クラス数）と \(K\)（基準点）を読み取る
2. 各クラス \(i\)（\(i = 1, 2, \ldots, N\)）について：
   • その行から生徒数 \(M_i\) と各生徒の点数を読み取る
   • 点数が \(K\) 以上の生徒の人数をカウントする
   • カウント結果を出力する

計算量

• 時間計算量: \(O\left(\sum_{i=1}^{N} M_i\right)\)
  • 各生徒を1回ずつ確認するため、全生徒数に比例
  • 最大で \(O(10^6)\) 程度
• 空間計算量: \(O\left(\max(M_i) + \text{入力全体}\right)\)
  • 各クラスの処理時に、そのクラスの点数リストを保持
  • 入力を一括で読み込む場合は入力全体のサイズ分のメモリを使用

実装のポイント

1. 入力の高速化: sys.stdin.read() を使って入力を一括で読み込むことで、大量のデータを効率的に処理できます。

2. 入力形式の注意: 各行の先頭が生徒数 \(M_i\) であり、その後に \(M_i\) 個の点数が続きます。line[0] が生徒数、line[1:] が点数リストとなります。

3. カウント処理: Pythonでは sum(1 for s in scores if s >= K) という書き方で、条件を満たす要素の個数を簡潔にカウントできます。これは以下と同等です：

   count = 0
   for s in scores:
      if s >= K:
          count += 1
   

   ソースコード

import sys

def main():
    input_data = sys.stdin.read().split('\n')
    first_line = input_data[0].split()
    N = int(first_line[0])
    K = int(first_line[1])
    
    for i in range(1, N + 1):
        line = list(map(int, input_data[i].split()))
        M = line[0]
        scores = line[1:M + 1]
        count = sum(1 for s in scores if s >= K)
        print(count)

if __name__ == "__main__":
    main()

---

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