概要

\(N\) 個のクラスに所属する全生徒のうち、点数が合格ライン \(K\) 以上である生徒の総数を求める問題です。

考察

この問題で求められているのは、非常にシンプルに言えば「与えられた全ての点数の中で \(K\) 以上のものがいくつあるか」を数えることです。

一見すると、クラスごとに生徒の人数 \(A_i\) が異なり、入力の形式が少し複雑に見えるかもしれません。しかし、本質的には以下の手順で解くことができます。

1. 合格者数を数えるための変数（カウンター）を \(0\) で用意する。
2. 各クラス \(i\) について、以下の操作を \(N\) 回繰り返す。
   • クラスの人数 \(A_i\) を確認する。
   • そのクラスの生徒 \(A_i\) 人分の点数を一つずつ確認し、\(K\) 以上であればカウンターを \(1\) 増やす。
3. 最終的なカウンターの値を表示する。

制約を確認すると、生徒の総数（\(\sum A_i\)）は最大で \(10^6\) です。全ての点数を 1 回ずつ確認する素直な方法（計算量 \(O(\sum A_i)\)）であれば、制限時間内に十分に間に合います。

アルゴリズム

以下の手順で実装します。

1. 入力の読み込み: Pythonでは、sys.stdin.read().split() を使うと、改行やスペースを区切りとして全ての数値を一つのリストとして取得できます。これにより、行ごとに人数が異なる入力も扱いやすくなります。
2. データの走査:
   • 最初の2つの値（\(N, K\)）を取得します。
   • 次に、各クラスの人数 \(A_i\) を読み取り、その直後の \(A_i\) 個の数値を点数として判定します。
   • 点数が \(K\) 以上なら答えに \(1\) 加算します。
3. 結果の出力: 全ての点数を確認し終えたら、合計人数を出力します。

計算量

• 時間計算量: \(O(N + \sum A_i)\) 全ての点数およびクラスごとの人数を 1 回ずつ確認するため、入力される数値の総数に比例した時間で計算が終わります。
• 空間計算量: \(O(N + \sum A_i)\) 全ての入力を一度にリスト（tokens）に格納するため、入力の総量に比例したメモリを使用します。

実装のポイント

• 可変長引数の扱い: クラスによって生徒の人数が異なりますが、リストのインデックスを管理する変数（コード中の idx）を用意して順番に読み進めることで、複雑な二次元リストなどを作ることなく、一つのリストとして効率的に処理できます。

• 高速な入力: input() を何度も呼び出すよりも、sys.stdin.read().split() で一括して読み込む方が、データ量が多い場合には実行時間が短縮されます。

  ソースコード

import sys

def solve():
    # 全ての入力を読み込み、スペースや改行で分割してトークンのリストを作成
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 全てのトークンを整数に変換
    tokens = list(map(int, data))
    
    # 最初の2つのトークンはクラス数 N と合格ライン K
    N = tokens[0]
    K = tokens[1]
    
    ans = 0
    idx = 2
    # 各クラスについて処理を繰り返す
    for _ in range(N):
        # tokens[idx] はそのクラスの人数 A_i
        A_i = tokens[idx]
        idx += 1
        # そのクラスの生徒の点数 B_{i,j} を順にチェック
        for _ in range(A_i):
            if tokens[idx] >= K:
                ans += 1
            idx += 1
            
    # 合計の合格者数を出力
    print(ans)

if __name__ == '__main__':
    solve()

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