概要

\(N\) 人の生徒と \(M\) 件の試験結果が与えられたとき、1回以上試験を受けた生徒のうち、平均点が閾値 \(T\) 未満である生徒の人数を求める問題です。

考察

この問題を解くためには、各生徒ごとに「これまでの合計点」と「受けた試験の回数」を正確に記録する必要があります。

1. データの管理方法 生徒の人数 \(N\) と試験の件数 \(M\) は最大で \(10^5\) と大きいため、生徒一人ひとりの情報を効率よく管理する必要があります。出席番号をインデックス（添え字）として、配列（リスト）で「合計点」と「試験回数」を保持するのが効率的です。

2. 平均値の判定と誤差の回避 平均値は 合計点 / 試験回数 で計算できますが、プログラミングにおいて小数の比較は「浮動小数点数」の精度による誤差が生じる可能性があります。 今回の条件は \(\frac{\text{合計点}}{\text{試験回数}} < T\) です。この式の両辺に 試験回数（正の数）を掛けると、以下のようになります。 $\(\text{合計点} < T \times \text{試験回数}\)$ このように整数の掛け算に変換することで、誤差を完全に排除して判定を行うことができます。

3. 「1件も提出していない生徒」の除外 問題文の条件に「1件も答案を提出していない生徒は要補習生徒に含めない」とあります。判定を行う際に、試験回数が 0 より大きいことを必ず確認する必要があります。

アルゴリズム

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

1. サイズ \(N+1\) の配列 total_scores（合計点用）と test_counts（試験回数用）を 0 で初期化します。
2. \(M\) 件の試験結果を順番に読み込み、出席番号 \(c_i\) の生徒に対応する配列の値を更新します。
   • total_scores[c_i] += s_i
   • test_counts[c_i] += 1
3. 出席番号 \(1\) から \(N\) までの生徒について、以下の条件を両方満たすか判定します。
   • test_counts[i] > 0 （試験を1回以上受けている）
   • total_scores[i] < T * test_counts[i] （平均が \(T\) 未満）
4. 条件を満たす生徒の総数を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みと試験結果の集計に \(O(M)\)、各生徒の判定に \(O(N)\) かかります。制約の \(10^5\) に対して十分高速に動作します。
• 空間計算量: \(O(N)\)
  • 各生徒の合計点と回数を保存するための配列のサイズが \(N\) に比例します。

実装のポイント

• 高速な入出力: \(M\) が大きいため、Python では sys.stdin.read().split() などを用いて入力を一括で読み込むと実行時間を短縮できます。

• 1-indexed の扱い: 出席番号が \(1\) から始まるため、配列のサイズを \(N+1\) で確保すると、出席番号をそのままインデックスとして扱えるため実装ミスを防げます。

• 判定式: 考察で述べた通り、小数を避けるために 合計点 < T * 試験回数 の形で比較を行います。

  ソースコード

import sys

def solve():
    # 全ての入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 基本情報の取得
    N = int(input_data[0])
    M = int(input_data[1])
    T = int(input_data[2])
    
    # 各生徒の合計点と提出数を管理する配列
    # インデックスを生徒の出席番号(1〜N)に合わせるため N+1 のサイズを確保
    total_scores = [0] * (N + 1)
    test_counts = [0] * (N + 1)
    
    # 答案情報の処理
    # 入力データは N, M, T の後、c_i, s_i のペアが続く
    idx = 3
    for _ in range(M):
        c = int(input_data[idx])
        s = int(input_data[idx + 1])
        total_scores[c] += s
        test_counts[c] += 1
        idx += 2
        
    remedial_students = 0
    
    # 各生徒について判定
    for i in range(1, N + 1):
        # 答案を1件以上提出している生徒のみ対象
        if test_counts[i] > 0:
            # 平均値 < T は、合計点 < T * 提出数 と同値（浮動小数点の誤差回避）
            if total_scores[i] < T * test_counts[i]:
                remedial_students += 1
                
    # 結果の出力
    print(remedial_students)

if __name__ == "__main__":
    solve()

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