概要

生徒の点数を更新しながら、最終的に補習が必要な生徒の人数を求める問題です。

考察

この問題では、最初に各生徒の点数が与えられ、その後いくつかの更新操作によって特定の生徒の点数が変更されます。すべての更新が終わった後に、点数が \(K\) 点未満の生徒の人数を数える必要があります。

素朴な方法としては、毎回の更新ごとに補習対象者を数えるといったことが考えられますが、それは不要な計算を多く含み、効率的ではありません。また、点数の上限が \(100\) 点であることから、点数の範囲が限られていることに気づけますが、この性質は今回の問題では直接的な高速化にはつながりません。

最もシンプルかつ効率的な方法は、すべての更新を配列上でそのまま処理し、最後に一度だけ全生徒の点数を見て補習対象者を数えることです。これにより、不要な計算を避けることができ、十分高速に動作します。

アルゴリズム

1. 最初に \(N\) 人の生徒の初期点数をリスト scores に格納します。
2. 次に、\(M\) 回の更新について、指定された生徒の点数を新しい値に上書きします。このとき、入力で与えられる生徒番号は 1-indexed なので、リストのインデックス（0-indexed）に合わせるために 1 を引きます。
3. すべての更新が終わったら、リスト内の各点数に対して、それが \(K\) 未満かどうかを判定し、該当する人数をカウントします。
4. カウント結果を出力します。

例えば、以下のような入力の場合：

3 2 60
50 70 80
1 65
3 40

• 初期状態: [50, 70, 80]
• 1 回目の更新（生徒 1 の点数を 65 に）→ [65, 70, 80]
• 2 回目の更新（生徒 3 の点数を 40 に）→ [65, 70, 40]
• 最終的に 60 点未満の人は 1 人（生徒 3）になります。

計算量

• 時間計算量: \(O(N + M)\)
  • 初期点数の読み込みに \(O(N)\)、更新処理に \(O(M)\)、最後のカウントに \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 生徒の点数を保持するリスト scores に \(O(N)\) のメモリを使用します。

実装のポイント

• 生徒の番号は 1-indexed で与えられるので、リストのインデックスにアクセスする際には必ず 1 を引く必要があります。

• 最後のカウント処理は、更新処理がすべて終わった後に行うのが重要です。

  ソースコード

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

# 更新処理
for _ in range(M):
    p, v = map(int, input().split())
    scores[p - 1] = v

# 補習対象の人数をカウント
count = 0
for score in scores:
    if score < K:
        count += 1

# 結果を出力
print(count)

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