公式

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

Claude 4.6 Opus (Thinking)

概要

\(N\) 人の生徒のスコアを管理し、スコアの移動・範囲内での比較カウント・範囲一斉加点の3種類のクエリを処理する問題です。制約が \(N, Q \leq 5000\) と小さいため、愚直なシミュレーションで解くことができます。

考察

まず制約を確認しましょう。\(N \leq 5000\)、\(Q \leq 5000\) です。

各クエリについて最悪の計算量を考えます:

  • 種類 1(スコアの移動): 2つの生徒のスコアを更新するだけなので \(O(1)\) です。
  • 種類 2(比較の問い合わせ): 区間 \([l, r]\) の各生徒について基準値と比較するため、最悪 \(O(N)\) です。
  • 種類 3(一斉加点): 区間 \([l, r]\) の各生徒にスコアを加算するため、最悪 \(O(N)\) です。

全体の計算量は最悪 \(O(NQ)\) で、\(5000 \times 5000 = 25{,}000{,}000\)(2500万)程度です。これは十分高速に動作する範囲なので、特別なデータ構造を使わず、配列を直接操作する愚直な方法で解けます。

もし \(N\) や \(Q\) がもっと大きければ(例えば \(10^5\) 以上)、セグメント木やBITなどの高度なデータ構造が必要になりますが、今回の制約ではその必要はありません。

アルゴリズム

  1. 長さ \(N+1\) の配列 score を用意し、全て \(0\) で初期化します(1-indexed で管理)。
  2. 各クエリを順に処理します:
    • 種類 1 (1 a b v): score[a] -= v、score[b] += v を実行します。
    • 種類 2 (2 x l r): score[x] を基準値として、\(i = l, l+1, \dots, r\) について score[i] > base となる個数を数えます。
    • 種類 3 (3 l r v): \(i = l, l+1, \dots, r\) について score[i] += v を実行します。
  3. 種類 2 のクエリの結果を順に出力します。

具体例

例えば \(N=3\) で、スコアが [0, 0, 0](生徒1〜3)のとき:

  • クエリ 1 1 2 5 → スコアは [-5, 5, 0]
  • クエリ 3 1 3 3 → スコアは [-2, 8, 3]
  • クエリ 2 3 1 3 → 基準値は score[3] = 3。区間 \([1, 3]\) でスコアが \(3\) より大きい生徒は生徒2(スコア \(8\))の1人 → 出力 1

計算量

  • 時間計算量: \(O(NQ)\)(各クエリで最悪 \(O(N)\) の走査が \(Q\) 回)
  • 空間計算量: \(O(N)\)(スコア配列の管理)

実装のポイント

  • スコアの絶対値が最大 \(10^{13}\) に達しうるため、C++ などでは long long を使う必要がありますが、Python では整数のオーバーフローを気にする必要がありません。

  • 種類 2 と種類 3 のクエリは引数の並び順が異なる(種類 2 は x l r、種類 3 は l r v)点に注意が必要です。問題文にも注意書きがあります。

  • 出力を一括で行うことで、I/O のオーバーヘッドを軽減しています(sys.stdout.write でまとめて出力)。

    ソースコード

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    score = [0] * (N + 1)  # 1-indexed
    
    results = []
    
    for _ in range(Q):
        query = list(map(int, input().split()))
        t = query[0]
        
        if t == 1:
            a, b, v = query[1], query[2], query[3]
            score[a] -= v
            score[b] += v
        elif t == 2:
            x, l, r = query[1], query[2], query[3]
            base = score[x]
            count = 0
            for i in range(l, r + 1):
                if score[i] > base:
                    count += 1
            results.append(count)
        else:  # t == 3
            l, r, v = query[1], query[2], query[3]
            for i in range(l, r + 1):
                score[i] += v
    
    sys.stdout.write('\n'.join(map(str, results)) + '\n' if results else '')

main()

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