概要

各生徒について提出した答案の平均点が閾値 \(T\) 未満かを判定し、（未提出者を除いて）要補習生徒の人数を数える問題です。

考察

各生徒 \(i\) の答案が \(k\) 件あり、得点が \(a_1, a_2, \dots, a_k\) だとすると平均点は \(\dfrac{a_1+\cdots+a_k}{k}\) です。これが \(T\) 未満かどうかを全生徒について判定します。

ここで重要なのは次の2点です。

1. 生徒ごとに「合計点」と「提出回数」だけ分かれば平均の比較ができる
   平均点の判定に必要なのは

   • 合計点 \(S=\sum a_j\)
   • 件数 \(k\) だけです。全得点を保存しておく必要はありません。

2. 浮動小数（小数）を使わずに比較できる
   \(\dfrac{S}{k} < T\) は、両辺に \(k(>0)\) を掛けて
   \(S < T \cdot k\)
   と同値です。これなら整数のまま比較でき、誤差も出ません。

また、「1件も提出していない生徒は除外」という条件があるので、\(k=0\) の場合は判定対象にしない点に注意が必要です。

素朴に「生徒ごとに得点のリストを持って平均を計算する」でも \(M \le 10^5\) なので間に合いますが、不要なメモリを使います。合計と件数のみを持つ方法が最もシンプルで効率的です。

アルゴリズム

1. 長さ \(N\) の配列を2つ用意する（1-indexed）。
   • sums[i]: 生徒 \(i\) の得点合計
   • cnts[i]: 生徒 \(i\) の提出回数
2. \(M\) 件の答案について、入力 \((c, s)\) ごとに
   • sums[c] += s
   • cnts[c] += 1
3. 生徒 \(i=1..N\) について
   • cnts[i] == 0 なら未提出なのでスキップ
   • そうでなく sums[i] < T * cnts[i] なら要補習としてカウント
4. カウントした人数を出力する。

例：生徒Aが 40点, 60点 の2回提出なら \(S=100, k=2\)。
平均 \(50\) が \(T=55\) 未満かは \(100 < 55 \times 2 = 110\) で判定できます。

計算量

• 時間計算量: \(O(N+M)\)（集計に \(O(M)\)、判定に \(O(N)\)）
• 空間計算量: \(O(N)\)（合計と件数の配列）

実装のポイント

• 平均比較は \(\dfrac{S}{k}\) を計算せず、必ず sums[i] < T * cnts[i] の形で整数比較する（誤差防止）。

• 未提出者（cnts[i] == 0）は要補習に含めない条件を忘れない。

• 入力が大きいので、sys.stdin.buffer.read() でまとめて読み取ると高速です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    M = next(it)
    T = next(it)

    sums = [0] * (N + 1)
    cnts = [0] * (N + 1)

    for _ in range(M):
        c = next(it)
        s = next(it)
        sums[c] += s
        cnts[c] += 1

    ans = 0
    for i in range(1, N + 1):
        c = cnts[i]
        if c and sums[i] < T * c:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。