概要

全クラスの全生徒の点数を調べ、合格ライン \(K\) 点以上の生徒が何人いるかを数える問題です。

考察

この問題は、与えられた全ての点数を確認し、条件を満たすものをカウントするシンプルな集計問題です。

重要な気づき

1. 入力形式の理解: 各行の最初に生徒数 \(A_i\) が与えられ、その後に \(A_i\) 個の点数が続きます
2. 全生徒を漏れなく確認: 全クラスを順番に処理し、各クラスの全生徒の点数をチェックします
3. 判定条件: 点数が \(K\) 点「以上」なので、\(B_{i,j} \geq K\) を満たすかどうかを判定します

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

• 全生徒数の合計は最大 \(10^6\) 人
• 各生徒について \(K\) 点以上かの判定は \(O(1)\) で可能
• よって、単純に全員をチェックする方法で十分間に合います

ただし、入力の読み込み方法には注意が必要です。Pythonで1行ずつ input() を呼ぶと、大量の入力に対しては遅くなる場合があります。

アルゴリズム

1. 最初に \(N\)（クラス数）と \(K\)（合格ライン）を読み込む
2. 合格者数をカウントする変数 count を 0 で初期化
3. 各クラス \(i\)（\(i = 1, 2, \ldots, N\)）について：
   • そのクラスの生徒数 \(A_i\) を読み込む
   • \(A_i\) 人分の点数を順に読み込む
   • 各点数 \(B_{i,j}\) について、\(B_{i,j} \geq K\) なら count を 1 増やす
4. 最終的な count を出力

具体例

入力例：

2 60
3 55 70 80
2 59 60

• クラス1：3人の点数は 55, 70, 80 → 60点以上は 70, 80 の2人
• クラス2：2人の点数は 59, 60 → 60点以上は 60 の1人
• 合計：\(2 + 1 = 3\) 人

計算量

• 時間計算量: \(O\left(\sum_{i=1}^{N} A_i\right)\)
  • 全生徒の点数を1回ずつ確認するため
  • 最大で \(10^6\) 回の処理
• 空間計算量: \(O\left(\sum_{i=1}^{N} A_i\right)\)
  • 入力データを一度に読み込むため
  • 1行ずつ処理すれば \(O(\max A_i)\) に削減可能

実装のポイント

1. 高速な入力処理: sys.stdin.read() で入力を一括読み込みし、split() で分割することで、大量の入力を高速に処理できます

2. インデックス管理: 入力データを配列として持ち、idx 変数で現在の読み込み位置を管理します。これにより、各行の構造（最初に生徒数、その後に点数）を柔軟に処理できます

3. カウント方法: 各点数を読み込むたびに即座に判定してカウントすることで、点数を全て保存する必要がなくなります（メモリ効率が良い）

   ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx])
    idx += 1
    K = int(input_data[idx])
    idx += 1
    
    count = 0
    for _ in range(N):
        A = int(input_data[idx])
        idx += 1
        for _ in range(A):
            B = int(input_data[idx])
            idx += 1
            if B >= K:
                count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

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