公式

A - 成績管理システム / Grade Management System 解説 by admin

Gemini 3.0 Flash (Thinking)

概要

\(N\) 人の生徒のスコアを、「2点間のスコア移動」「範囲内の生徒への一斉加点」「特定の生徒を基準とした範囲内の比較」という3種類のクエリで管理する問題です。

考察

この問題の制約は \(N \le 5000, Q \le 5000\) です。クエリごとに最大 \(O(N)\) の処理を行っても、全体の計算量は \(O(QN) \approx 2.5 \times 10^7\) 程度となります。Pythonなどの言語ではこの計算量は工夫なしでは実行時間制限に間に合わない可能性がありますが、適切なデータ構造と実装の工夫によって \(O(QN)\) のアルゴリズムで正解を得ることができます。

各クエリの性質

  1. 種類 1(点更新): 2人の生徒のスコアを個別に変更します。これは \(O(1)\) で処理可能です。
  2. 種類 2(範囲比較): 指定された範囲 \([l, r]\) の生徒を一人ずつ確認する必要があります。最悪で \(O(N)\) かかります。
  3. 種類 3(範囲加算): 範囲内の全員に加点します。愚直にループを回すと \(O(N)\) かかりますが、差分配列(いもす法)の考え方を使うことで、更新自体は \(O(1)\) で行うことができます。

効率化のポイント

種類 2 のクエリが連続する場合や、更新クエリの後に複数回の比較がある場合、毎回すべてのスコアを再計算するのは非効率です。そこで、「スコアに変更があったか」を管理するフラグ(dirty フラグ)を用意し、種類 2 のクエリが来たときに必要な場合のみ最新のスコアを計算し直す手法(遅延評価に近い考え方)が有効です。

アルゴリズム

以下の手順でクエリを処理します。

  1. データの保持:

    • 点更新用の配列 scores: 種類 1 のクエリの結果を保持します。
    • 範囲更新用の差分配列 D: 種類 3 のクエリを高速に処理するために使用します。
    • キャッシュ用配列 actual_scores: 全生徒の現在の合計スコアを格納します。
  2. クエリの処理:

    • 種類 1: scores[a] を減らし、scores[b] を増やします。変更があったため dirty フラグを立てます。
    • 種類 3: 差分配列 D の l 番目を増やし、r+1 番目を減らします。これも dirty フラグを立てます。
    • 種類 2:
      • dirty フラグが立っていれば、差分配列 D の累積和をとり、scores と合算して actual_scores を最新の状態に更新します。
      • 更新後、actual_scores[x] を基準値とし、範囲 [l, r] を走査して基準値より大きい人数をカウントします。

計算量

  • 時間計算量: \(O(QN)\)
    • 各クエリの処理は最大で \(O(N)\) です。\(N, Q \le 5000\) のため、全体で約 \(2.5 \times 10^7\) 回の操作となり、効率的に実装された Python コードであれば制限時間内に収まります。
  • 空間計算量: \(O(N)\)
    • 生徒のスコアを保持するための長さ \(N\) の配列を数個使用します。

実装のポイント

  • 高速な入出力: sys.stdin.read().split() で入力を一括で読み込み、sys.stdout.write で一括出力することで、Python の入出力ボトルネックを解消します。

  • スライスの活用: 種類 2 のカウント処理において、actual_scores[l:r+1] のようにスライスを用いることで、Python の内部的な最適化が効き、通常の for ループよりも高速に動作します。

  • 差分配列の活用: 種類 3 の範囲加算を \(O(1)\) で行うことで、更新クエリが連続した際の無駄な計算を省いています。

    ソースコード

import sys

# 競技プログラミングのエキスパートとして、効率的なO(QN)のアルゴリズムを実装します。
# Python 3での実行速度を考慮し、不要な計算を避け、高速なI/Oとローカル変数の活用、
# 差分配列(Difference Array)による範囲更新の最適化を行っています。

def solve():
    # 標準入力からすべてのデータを一括で読み込み、整数リストに変換して高速化を図ります。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    data = [int(x) for x in input_data]
    
    N = data[0]
    Q = data[1]
    
    # scores は種類1(点更新)によるスコアの変動を保持します。
    scores = [0] * (N + 1)
    # D は種類3(範囲加点)を効率的に扱うための差分配列です。
    D = [0] * (N + 2)
    # actual_scores は各生徒の最新の合計スコアをキャッシュするために使用します。
    actual_scores = [0] * (N + 1)
    # dirty フラグは、前回の問い合わせ以降にスコアが変更されたかどうかを管理します。
    dirty = True
    
    ptr = 2
    results = []
    results_append = results.append
    
    # 各クエリを時系列順に処理します。
    for _ in range(Q):
        q_type = data[ptr]
        
        if q_type == 1:
            # 種類 1:スコアの移動 (点更新)
            # 生徒 a のスコアを v 減らし、生徒 b のスコアを v 増やす。
            a = data[ptr+1]
            b = data[ptr+2]
            v = data[ptr+3]
            scores[a] -= v
            scores[b] += v
            dirty = True
            ptr += 4
            
        elif q_type == 2:
            # 種類 2:スコアの比較に関する問い合わせ (範囲クエリ)
            # 生徒 x のスコアを基準とし、[l, r] の範囲で基準より大きい人数を数える。
            x = data[ptr+1]
            l = data[ptr+2]
            r = data[ptr+3]
            
            # スコアが変更されている場合のみ、全生徒の最新スコアを再計算します。
            if dirty:
                curr_diff_sum = 0
                for i in range(1, N + 1):
                    curr_diff_sum += D[i]
                    actual_scores[i] = scores[i] + curr_diff_sum
                dirty = False
            
            target = actual_scores[x]
            count = 0
            
            # Pythonにおいて、スライスによるイテレーションは通常のインデックスアクセスより高速です。
            # このループが全体のボトルネックとなりますが、N, Q <= 5000 では十分に間に合います。
            sub_range_scores = actual_scores[l:r+1]
            for s in sub_range_scores:
                if s > target:
                    count += 1
            results_append(str(count))
            ptr += 4
            
        elif q_type == 3:
            # 種類 3:一斉加点 (範囲更新)
            # 差分配列 D を用いることで、範囲加点を O(1) で処理します。
            l = data[ptr+1]
            r = data[ptr+2]
            v = data[ptr+3]
            D[l] += v
            D[r+1] -= v
            dirty = True
            ptr += 4
            
    # すべての問い合わせ結果をまとめて出力します。
    if results:
        sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

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