概要

各生徒の提出した答案の平均点が閾値 \(T\) 未満である生徒の人数を求める問題です。答案を1つも提出していない生徒は対象外です。

考察

問題を解くためには、各生徒に対して以下の情報を管理する必要があります： - その生徒が提出した答案の合計点数 - 提出した答案の数

これらの情報があれば、平均点を計算して閾値 \(T\) と比較できます。重要な点は、答案を1つも提出していない生徒は要補習生徒に含めないことです。

素朴なアプローチとして、2次元配列ですべての答案を生徒ごとに保持する方法が考えられますが、\(N\) と \(M\) が最大 \(10^5\) まで大きくなるため、メモリ使用量や計算効率の観点から適切ではありません。代わりに、各生徒の合計点数と答案数を個別に管理することで、効率的に処理できます。

アルゴリズム

1. 各生徒の合計点数と答案数を記録するためのデータ構造（ここでは辞書）を用意します。
2. 入力された答案情報を1件ずつ処理します：
   • 生徒番号 \(c_i\) をキーとして、合計点数に \(s_i\) を加算し、答案数を1増やします。
3. すべての生徒（1から \(N\) まで）についてループし、答案を1つ以上提出している生徒のみを対象に平均点を計算します：
   • 平均点 = 合計点数 / 答案数
   • 平均点が \(T\) 未満ならば、要補習生徒としてカウントします。
4. 要補習生徒の総数を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 答案情報の処理に \(O(M)\)、生徒のチェックに \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 最大 \(N\) 人の生徒の情報を保持するためです。

実装のポイント

• 答案を提出していない生徒（辞書に存在しないキー）の処理に注意します。答案を提出していない生徒はスキップします。

• 整数除算ではなく浮動小数点数除算を使用して平均を計算します（問題文の条件通り）。

• 入力データが大きい可能性があるため、sys.stdin.read() で一括読み込みを行うことで効率化しています。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    m = int(data[1])
    T = int(data[2])
    
    scores = {}
    
    index = 3
    for i in range(m):
        c = int(data[index])
        s = int(data[index + 1])
        index += 2
        
        if c not in scores:
            scores[c] = []
        scores[c].append(s)
    
    count = 0
    for student in range(1, n + 1):
        if student in scores:
            total = sum(scores[student])
            average = total / len(scores[student])
            if average < T:
                count += 1
                
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。