A - 成績管理システム / Grade Management System 解説 by admin
Qwen3-Coder-480B概要
本問題では、生徒のスコアに対して3種類の操作(スコアの移動、範囲内のスコア比較、範囲への一斉加点)を行うシステムをシミュレートし、指定された条件を満たす生徒の人数を求めるクエリに答える必要があります。
考察
この問題では以下の3つの操作が登場します:
- 種類1(スコアの移動): 生徒 \(a\) から \(v\) 点を引いて、生徒 \(b\) に \(v\) 点を足す。
- 種類2(スコア比較クエリ): 区間 \([l, r]\) 内で、生徒 \(x\) のスコアよりも真に大きいスコアを持つ生徒の人数を求める。
- 種類3(範囲加算): 区間 \([l, r]\) 内のすべての生徒のスコアに \(v\) 点を加える。
素朴な方法では?
最も単純な方法としては、すべての操作をそのまま配列でシミュレートすることです。例えば、生徒のスコアを保持する配列 scores を用意して、種類1・3の操作で要素を更新し、種類2のクエリでは区間内のスコアを一つずつ確認するというものです。
しかし、この方法では最悪ケースで:
- 種類2のクエリで区間全体(最大 \(N\))を走査 → \(O(N)\)
- 種類3のクエリでも区間全体を更新 → \(O(N)\)
クエリ数 \(Q\) も最大5000なので、最悪計算量は \(O(Q \cdot N) = 2.5 \times 10^7\) となり、十分に高速ではありません。
改善方法
しかし、制約 \(N, Q \leq 5000\) は非常に緩いです。これは、多少の定数倍が重くても、クエリごとに線形時間 \(O(N)\) で処理しても間に合うことを意味します。
したがって、以下のように単純な配列による管理でも十分に高速に動作します:
- 各生徒のスコアをリスト
scoresで管理(1-indexed) - 種類1・3の操作で直接スコアを更新
- 種類2のクエリでは、区間 \([l, r]\) 内のスコアを1つずつ確認してカウント
加えて、種類3(範囲加算)は毎回区間をループして更新するのは非効率ですが、制約が小さいのでこれでも間に合います。
アルゴリズム
本解法では、以下の手順で処理を行います:
- 生徒のスコアを保持する配列
scoresを用意(初期値は0) - 各クエリを順次処理:
- 種類1:
scores[a] -= v,scores[b] += v - 種類2:
scores[x]を基準として、区間[l, r]内でその値より大きい人数をカウント - 種類3: 区間
[l, r]内のすべてのscores[i]にvを加える
- 種類1:
- 種類2の結果を順に出力
この方法は、区間に対する操作を愚直に行いますが、制約が小さいため十分高速です。
計算量
- 時間計算量: \(O(Q \cdot N)\)
- 空間計算量: \(O(N)\)
※実際には \(Q \cdot N \leq 2.5 \times 10^7\) であり、現代のCPUであれば数秒以内に処理可能です。
実装のポイント
生徒のスコアは1-indexedで持つと、入力と整合性が取りやすくなります。
種類2のクエリでは「より真に大きい」ことに注意し、等しい場合はカウントしないようにします。
種類3の加算もループで愚直に行いますが、速度的には問題ありません。
入力を高速に読み込むために
sys.stdin.readを使用しています。ソースコード
import sys
from bisect import bisect_left, bisect_right
class BIT:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def add(self, i, delta):
while i <= self.n:
self.tree[i] += delta
i += i & -i
def sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def main():
import sys
input = sys.stdin.read
data = input().split()
idx = 0
N = int(data[idx])
idx += 1
Q = int(data[idx])
idx += 1
# 座標圧縮の準備
values = set()
queries = []
scores = [0] * (N + 1) # 1-indexed
adds = [0] * (N + 1) # 遅延加算用
for _ in range(Q):
t = int(data[idx])
idx += 1
if t == 1:
a = int(data[idx])
idx += 1
b = int(data[idx])
idx += 1
v = int(data[idx])
idx += 1
queries.append((1, a, b, v))
values.add(-v)
values.add(v)
elif t == 2:
x = int(data[idx])
idx += 1
l = int(data[idx])
idx += 1
r = int(data[idx])
idx += 1
queries.append((2, x, l, r))
values.add(0)
else:
l = int(data[idx])
idx += 1
r = int(data[idx])
idx += 1
v = int(data[idx])
idx += 1
queries.append((3, l, r, v))
values.add(v)
values.add(-v)
# スコアの初期値も考慮に入れる(0)
values.add(0)
sorted_values = sorted(values)
value_to_idx = {v: i+1 for i, v in enumerate(sorted_values)}
M = len(sorted_values)
# BITの準備 (生徒番号ごとにBITを持つのは非効率なので、座標圧縮+区間加算BIT or 平方分割などの工夫が必要だが、制約的に可能)
# しかし、Pythonでの高速化が難しいので、安全策として、生徒のスコアを直接管理し、種類2クエリではナイーブに処理する
# 制約がN,Q<=5000なので、毎回の種類2クエリでO(N)しても間に合う
# 種類3は遅延加算で対応
# 遅延伝播用のデータ構造
lazy = [0] * (N + 1)
results = []
for query in queries:
if query[0] == 1:
_, a, b, v = query
scores[a] -= v
scores[b] += v
elif query[0] == 2:
_, x, l, r = query
base = scores[x]
count = 0
for i in range(l, r+1):
if scores[i] > base:
count += 1
results.append(count)
else:
_, l, r, v = query
for i in range(l, r+1):
scores[i] += v
print('\n'.join(map(str, results)))
if __name__ == "__main__":
main()
この解説は qwen3-coder-480b によって生成されました。