概要

\(N\) 人の生徒のうち、提出した答案の平均点が閾値 \(T\) 未満である生徒（要補習生徒）の人数を求める問題です。答案を1件も提出していない生徒は対象外です。

考察

問題の整理

各答案には「誰が提出したか（出席番号）」と「得点」が記録されています。同じ生徒が複数回答案を提出している場合があるため、生徒ごとに得点を集計して平均を求める必要があります。

具体例で考える

例えば \(N=3, M=5, T=50\) で、以下の答案があったとします：

答案	生徒番号	得点
1	1	40
2	2	80
3	1	30
4	2	60
5	1	20

• 生徒1：得点合計 \(40+30+20=90\)、答案数 \(3\)、平均 \(90/3=30.0\) → \(30.0 < 50\) なので要補習
• 生徒2：得点合計 \(80+60=140\)、答案数 \(2\)、平均 \(140/2=70.0\) → \(70.0 \geq 50\) なので補習不要
• 生徒3：答案なし → 対象外

よって答えは 1 です。

素朴なアプローチで十分か？

各答案を1回ずつ読みながら生徒ごとに「得点の合計」と「答案数」を記録し、最後に全生徒について平均値を計算すればよいです。答案数 \(M\) 回のループと、答案を提出した生徒数（最大 \(N\)）回のループで済むため、\(O(N + M)\) で解けます。\(N, M \leq 10^5\) なので十分高速です。

アルゴリズム

1. 入力を読み込む: \(N, M, T\) および \(M\) 件の答案情報を取得する。
2. 生徒ごとに集計する: 辞書（defaultdict）を用いて、生徒ごとの「得点の合計 (total)」と「答案の提出数 (count)」を記録する。
3. 要補習生徒を数える: 答案を1件以上提出した生徒（count に登録されている生徒）について、\(\frac{\text{total}}{\text{count}} < T\) であれば要補習生徒としてカウントする。
4. 結果を出力する。

計算量

• 時間計算量: \(O(N + M)\)
  • \(M\) 件の答案を読み込みながら集計するのに \(O(M)\)、答案を提出した生徒（最大 \(N\) 人）について判定するのに \(O(N)\)。
• 空間計算量: \(O(N)\)
  • 生徒ごとの合計得点・答案数を記録する辞書に最大 \(O(N)\) のエントリが格納される。

実装のポイント

• defaultdict の活用: 生徒番号をキーとして、初期値 \(0\) で合計・個数を管理できるため、存在チェックが不要になり簡潔に書けます。

• 答案未提出の生徒の除外: count の辞書に登録されている生徒のみをループすることで、自然に「答案を1件も出していない生徒」を除外できます。全生徒 \(1\) から \(N\) をループする必要はありません。

• 浮動小数点の比較: 平均値 \(\frac{\text{total}}{\text{count}}\) と \(T\) を比較する際、Python では / 演算子が浮動小数点除算を行います。整数同士の比較で済ませたい場合は total[student] < T * count[student] と変形することもできますが、本問の制約（得点・閾値ともに \(100\) 以下、答案数 \(10^5\) 以下）では浮動小数点誤差の心配はありません。

  ソースコード

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1

    total = defaultdict(int)
    count = defaultdict(int)

    for _ in range(M):
        c = int(input_data[idx]); idx += 1
        s = int(input_data[idx]); idx += 1
        total[c] += s
        count[c] += 1

    ans = 0
    for student in count:
        if total[student] / count[student] < T:
            ans += 1

    print(ans)

main()

---

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