概要

\(N\) 人の生徒の初期点数に対し、\(M\) 回の更新（点数の書き換え）を行った後、最終的な点数が \(K\) 点未満である生徒の総数を求める問題です。

考察

この問題で重要なのは、「ある生徒に対して複数回の更新が行われた場合、最後に実行された更新だけが有効になる」という点です。

効率的な処理の必要性

生徒数 \(N\) と更新回数 \(M\) は共に最大 \(10^5\) です。 - 愚直に「更新のたびに全生徒の点数を確認して補習対象者を数える」という処理をすると、計算量は \(O(N \times M)\) となり、最大で \(10^{10}\) 回程度の計算が必要になります。これは一般的な制限時間（2秒）には間に合いません。 - そこで、「すべての更新を反映させた後の最終的な状態」を一度だけ作り、最後に \(1\) 回だけ集計を行うアプローチをとります。これなら \(O(N + M)\) の計算量で済み、十分に間に合います。

更新の管理

提示されたコードでは、更新情報を管理するために辞書（ハッシュマップ）を利用しています。辞書に 生徒番号: 点数 という形式で保存することで、同じ生徒番号に対して新しい点数が来るたびに値が上書きされ、自然と「最後の更新内容」だけを残すことができます。

アルゴリズム

以下の手順で解いています。

1. 初期データの読み込み: 生徒数 \(N\)、更新回数 \(M\)、基準点 \(K\)、および各生徒の初期点数を取得します。
2. 更新情報の集約: \(M\) 個の更新クエリを順に読み込み、辞書 final_updates に格納します。これにより、各生徒の最終的な更新後の点数が確定します。
3. 補習対象者の集計: 生徒を「更新があった生徒」と「更新がなかった生徒」の2グループに分けてカウントします。
   • 更新があった生徒: 辞書 final_updates の値を調べ、\(K\) 点未満の人数を数えます。
   • 更新がなかった生徒: 初期点数のリストを調べ、その生徒の番号が辞書に含まれていない（＝更新されていない）かつ初期点数が \(K\) 点未満の人数を数えます。
4. 結果の出力: 2つのグループの合計人数を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みに \(O(N + M)\)、更新情報の辞書への登録に \(O(M)\)、最終的な集計（全生徒の走査）に \(O(N)\) かかります。辞書や集合（set）の操作は平均 \(O(1)\) であるため、全体として線形時間で処理可能です。
• 空間計算量: \(O(N + M)\)
  • 初期点数のリスト（\(N\)要素）と、最悪の場合すべての生徒が更新される際の辞書（\(M\)要素）を保持するためのメモリが必要です。

実装のポイント

• 高速な入力: sys.stdin.read().split() を使用することで、大量の入力データを一括で読み込み、高速に処理しています。

• データの区別: updated_ids = set(final_updates.keys()) を作成することで、「その生徒が更新されたかどうか」を \(O(1)\) で判定できるようにしています。

• 1-indexed への対応: 問題文では生徒番号が \(1\) から \(N\) で与えられるため、enumerate(initial_scores, 1) を使ってループのインデックスを \(1\) 始まりに調整しています。

  ソースコード

import sys

def main():
    # 入力データを一括で読み込み、イテレータとして処理します
    # これにより、大量の入力データに対しても効率的にアクセスできます
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    
    # 基本設定の読み込み
    n = int(next(it))
    m = int(next(it))
    k = int(next(it))
    
    # 各生徒の初期点数をリストとして保持します
    initial_scores = [int(next(it)) for _ in range(n)]
    
    # 更新情報を辞書形式で管理します。
    # キーを生徒番号、値を点数とすることで、同一生徒への複数回の更新があっても
    # 自然に「最後の更新内容」のみを保持することができます。
    final_updates = {}
    for _ in range(m):
        p = int(next(it))
        v = int(next(it))
        final_updates[p] = v
        
    # 更新が行われた生徒のIDを集合(set)として抽出します（O(1)での存在確認のため）
    updated_ids = set(final_updates.keys())
    
    # 最終的な補習対象者の集計
    # アプローチ：
    # 1. 更新があった生徒については、辞書に格納された「最終的な点数」を確認する
    # 2. 更新がなかった生徒については、初期点数リストの値をそのまま確認する
    
    # 更新があった生徒のカウント
    count_from_updates = sum(1 for score in final_updates.values() if score < k)
    
    # 更新がなかった生徒のカウント
    # enumerate(..., 1) を用いて1-indexedの生徒番号を取得します
    count_from_initial = sum(1 for i, score in enumerate(initial_scores, 1) 
                             if i not in updated_ids and score < k)
    
    # 合計人数を出力
    sys.stdout.write(str(count_from_updates + count_from_initial) + '\n')

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-preview によって生成されました。