概要

生徒の成績リストに対して複数回の更新を行い、最終的に基準点未満の生徒が何人いるかを数える問題です。

考察

問題の整理

この問題では、以下の手順で処理を行います： 1. \(N\) 人の生徒の初期点数を受け取る 2. \(M\) 回の更新（特定の生徒の点数を書き換える）を順番に適用する 3. 最終的に \(K\) 点未満の生徒の人数を数える

重要な気づき

• 同じ生徒が複数回更新される可能性があることに注意が必要です
• 例えば、生徒1の点数が「50→70→30」と2回更新された場合、最終的な点数は30点です
• つまり、各更新を順番に適用していけば、自然と最新の点数に上書きされます

この問題が易しい理由

• 複雑なアルゴリズムは不要で、単純にシミュレーション（指示通りに処理）すればOKです
• 各更新で配列の該当箇所を書き換えるだけなので、\(O(1)\) で処理できます

アルゴリズム

1. 初期化: 生徒の点数を配列 Q に格納する

2. 更新処理: \(M\) 回の更新を順番に処理する

   • 各更新では、生徒番号 \(P\) の点数を \(V\) に書き換える
   • 生徒番号は1から始まる（1-indexed）ので、配列のインデックス（0-indexed）に変換するため P - 1 とする

3. カウント: 最終的な配列 Q を走査し、\(K\) 点未満の生徒の人数を数える

具体例

入力例：\(N=3, M=2, K=50\)、初期点数 \([40, 60, 30]\) - 更新1: 生徒1の点数を55に → \([55, 60, 30]\) - 更新2: 生徒3の点数を70に → \([55, 60, 70]\) - 50点未満の生徒は0人

計算量

• 時間計算量: \(O(N + M)\)

  • 初期点数の読み込み: \(O(N)\)
  • \(M\) 回の更新処理: 各 \(O(1)\) なので合計 \(O(M)\)
  • 最終カウント: \(O(N)\)

• 空間計算量: \(O(N)\)

  • 生徒の点数を格納する配列のみ

実装のポイント

1. インデックスの変換: 問題文では生徒番号が1から始まる（1-indexed）のに対し、Pythonの配列は0から始まる（0-indexed）ため、Q[P - 1] のように調整が必要です

2. 更新回数が0の場合: \(M = 0\) の場合もあり得ますが、forループが0回実行されるだけなので特別な処理は不要です

3. カウントの書き方: Pythonでは sum(1 for score in Q if score < K) のようにジェネレータ式を使うと簡潔に書けます。len([score for score in Q if score < K]) でも同じ結果が得られます

   ソースコード

# 入力を受け取る
N, M, K = map(int, input().split())
Q = list(map(int, input().split()))

# M回の更新を処理
for _ in range(M):
    P, V = map(int, input().split())
    Q[P - 1] = V  # 生徒番号は1-indexedなので調整

# K点未満の生徒の人数をカウント
count = sum(1 for score in Q if score < K)

# 結果を出力
print(count)

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