公式
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などの高度なデータ構造が必要になりますが、今回の制約ではその必要はありません。
アルゴリズム
- 長さ \(N+1\) の配列
scoreを用意し、全て \(0\) で初期化します(1-indexed で管理)。 - 各クエリを順に処理します:
- 種類 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を実行します。
- 種類 1 (
- 種類 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 によって生成されました。