概要

\(N\) 人の生徒のうち、提出した答案の平均点が閾値 \(T\) 未満である「要補習生徒」の人数を求めます。ただし、一度も答案を出していない生徒は対象外です。

考察

この問題では、各生徒ごとに提出した答案の得点を集計し、その平均を計算して判定する必要があります。

素朴な方法としては、各生徒に対してその生徒の答案をすべて探して平均を出すということが考えられますが、これは生徒数 \(N\) と答案数 \(M\) の両方が最大 \(10^5\) なので、全探索では間に合いません（時間計算量が \(O(N \times M)\) になってしまう）。

そこで、各答案に含まれる生徒番号と得点のペアを読み込みながら、各生徒の得点リストを効率的に集計することが重要です。Python では collections.defaultdict を使うことで、キーに対応するリストが自動的に生成され、存在チェックなしに追加できます。

さらに、一度も答案を出していない生徒は無視する必要があるため、提出履歴がある生徒のみを処理するようにします。

最後に、各生徒の得点の合計と個数から平均を計算し、それが閾値 \(T\) より小さいかどうかを判定すればよいです。

アルゴリズム

1. 各答案の情報を読み込み、生徒番号ごとに得点をリストにまとめる（defaultdict(list) を使用）。
2. 各生徒（1 から \(N\) まで）について：
   • 提出した答案が存在するか確認。
   • 存在すれば、得点の平均を計算。
   • 平均が閾値 \(T\) 未満であればカウントアップ。
3. 最終的なカウントを出力。

計算量

• 時間計算量: \(O(M + N)\)
  各答案を1回ずつ処理し、その後各生徒を1回ずつ走査するので線形時間。
• 空間計算量: \(O(M)\)
  各答案の情報を保存するのに必要なメモリ量。

実装のポイント

• sys.stdin.read() を使って高速に入力を読み込む（input() だと遅い可能性があるため）。
• defaultdict(list) を使うことで、キーが存在しなくてもエラーにならずに得点を追加できる。
• 平均値の比較は浮動小数点数で行うが、整数同士の除算で問題ない。
• 答案を出していない生徒はスキップする条件を忘れずに。

## ソースコード

```python
import sys
from collections import defaultdict

input = sys.stdin.read
data = input().split()

N = int(data[0])
M = int(data[1])
T = int(data[2])

scores = defaultdict(list)

index = 3
for _ in range(M):
    c = int(data[index])
    s = int(data[index+1])
    scores[c].append(s)
    index += 2

count = 0
for student in range(1, N+1):
    if student in scores:
        avg = sum(scores[student]) / len(scores[student])
        if avg < T:
            count += 1

print(count)

この解説は qwen3-coder-480b によって生成されました。