概要

この問題は、\(N\) 個のクラスそれぞれについて、与えられた \(M_i\) 人の生徒の点数を確認し、基準点 \(K\) 以上の点数を取った生徒が何人いるかを数え上げる問題です。

考察

この問題のポイントは、データの全体量と入力形式の扱いにあります。

• 計算量について: 生徒の総数 \(\sum M_i\) は最大で \(10^6\) に達します。各生徒の点数を 1 回ずつ確認して基準点 \(K\) と比較する素直な方法をとれば、全体の計算回数は生徒の総数に比例します。これはプログラムが十分に制限時間内に終わる計算量です。
• 入力の受け取り方について: 各行ごとに「生徒数 \(M_i\)」と「\(M_i\) 個の点数」が並んでいます。行によって数値の個数が異なるため、1 行ずつ読み込んで処理するか、あらかじめ全ての数値をリストとして読み込んでから順番に処理していく工夫が必要です。

アルゴリズム

以下の手順で解を進めます。

1. データの読み込み: 効率化のため、標準入力からすべての数値を一気に読み込み、整数のリストに変換します。
2. 各クラスの処理: 現在の読み取り位置（インデックス）を管理しながら、以下の操作を \(N\) 回繰り返します。
   • そのクラスの生徒数 \(M_i\) を取得する。
   • 続く \(M_i\) 個の点数を一つずつ確認し、その値が \(K\) 以上であればカウントを 1 増やす。
   • カウントした結果を記録し、読み取り位置を次のクラスのデータの先頭まで進める。
3. 結果の出力: 各クラスのカウント結果を改行区切りでまとめて出力します。

計算量

• 時間計算量: \(O(N + \sum M_i)\) すべてのクラスを 1 回ずつ、すべての生徒の点数を 1 回ずつ確認するため、入力の総数に比例した時間で処理が完了します。
• 空間計算量: \(O(N + \sum M_i)\) 入力をすべてリストに格納する場合、そのデータ量に比例したメモリを使用します。

実装のポイント

• 高速な入出力: Python では、生徒数が多い場合に input() を何度も呼び出すと実行時間が長くなることがあります。sys.stdin.read().split() を使って一括で読み込み、最後に sys.stdout.write() で一括出力することで、大幅に高速化できます。

• インデックス管理: 可変長のデータを扱うため、次に読み込むべきデータの位置を変数（例：idx）で管理することで、複雑な入力形式にも柔軟に対応できます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのトークンを読み込み、整数のリストに変換します
    # sys.stdin.read().split() は空白（スペース、改行、タブ）で分割されたすべての単語をリストとして取得します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # mapを使用して一括で整数に変換することで、効率的に処理します
    data = list(map(int, input_data))
    
    # クラス数 N と基準点 K を取得
    N = data[0]
    K = data[1]
    
    # データの読み取り位置を管理するインデックス
    idx = 2
    
    # 各クラスの結果を格納するリスト
    results = []
    
    # N 個のクラスについて順番に処理を行います
    for _ in range(N):
        # クラス i の生徒数 M_i
        m = data[idx]
        idx += 1
        
        # クラス i の点数リストをスライスで取得し、K点以上の人数をカウントします
        # スライスとループの組み合わせはPythonにおいて効率的です
        count = 0
        class_scores = data[idx : idx + m]
        for score in class_scores:
            if score >= K:
                count += 1
        
        # カウントした結果を文字列としてリストに追加
        results.append(str(count))
        
        # インデックスを次のクラスのデータ位置まで進める
        idx += m
        
    # すべての結果を改行で連結して一気に出力します
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。