C - 周期的な追いかけっこ / Periodic Chase 解説 by admin
gpt-5.5-high概要
高橋君が青木君にどれだけ近づいたかを、各秒の差分 \(C_i = B_i - A_i\) として考えます。
周期ごとの合計と、周期内の累積和を使って、各クエリを \(O(N)\) で処理します。
考察
時刻 \(0\) での距離差は \(d\) です。
ある \(1\) 秒で青木君が \(A_i\)、高橋君が \(B_i\) 進むので、この \(1\) 秒で距離差は
\(B_i - A_i\)
だけ縮まります。
そこで、
\(C_i = B_i - A_i\)
とします。
時刻 \(t\) までに高橋君が青木君に近づいた合計を \(X(t)\) とすると、高橋君が追い付く条件は
\(X(t) \geq d\)
です。
周期 \(N\) の中での累積和を
\(P_i = C_1 + C_2 + \cdots + C_i\)
とします。
また、1 周期全体での増加量を
\(S = C_1 + C_2 + \cdots + C_N\)
とします。
時刻 \(t\) を
\(t = qN + r \quad (0 \leq r < N)\)
と表すと、\(q\) 周期終わったあとに周期内で \(r\) 秒進んだことになります。
このときの累積は
\(X(t) = qS + P_r\)
です。
素朴なシミュレーションでは間に合わない
各 2 d クエリで、1 秒ずつシミュレーションすると、答えが \(10^{15}\) 付近になる可能性があります。
そのため、時間をそのまま進める方法は使えません。
また、\(C_i\) は負になることもあるため、累積和 \(X(t)\) は単調増加とは限りません。
そのため、単純に二分探索することもできません。
1 周期の合計 \(S\) で場合分けする
\(S \leq 0\) の場合
1 周期ごとの合計が増えないので、後の周期に行っても、同じ周期内位置での累積値は増えません。
つまり、追い付けるなら最初の \(N\) 秒以内に必ず追い付きます。
したがって、\(P_1, P_2, \dots, P_N\) を順に見て、初めて \(d\) 以上になる場所を探せばよいです。
存在しなければ答えは \(-1\) です。
\(S > 0\) の場合
1 周期ごとには累積が増えるので、いつか必ず追い付けます。
ただし、周期の途中で追い付く可能性があるため、周期内の最大累積和が重要です。
1 周期内の最大値を
\(M = \max(P_0, P_1, \dots, P_N)\)
とします。
\(q\) 周期終わったあとの次の周期内で到達できる最大値は
\(qS + M\)
です。
したがって、追い付ける最初の周期番号 \(q\) は
\(qS + M \geq d\)
を満たす最小の \(q\) です。
もし \(d \leq M\) なら、最初の周期内で追い付けます。
そうでない場合は、
\(q = \left\lceil \frac{d - M}{S} \right\rceil\)
です。
この \(q\) 周期分を先に飛ばすと、残り必要な値は
\(d - qS\)
になります。
あとは周期内で初めて
\(P_i \geq d - qS\)
となる \(i\) を探せば、答えは
\(qN + i\)
です。
アルゴリズム
まず、各 \(i\) について
\(C_i = B_i - A_i\)
を持ちます。
また、周期全体の合計
\(S = \sum C_i\)
も管理します。
各クエリを以下のように処理します。
1 i a b
\(i\) 番目の値を更新します。
新しい差分は
\(b - a\)
です。
古い \(C_i\) との差分だけ、周期合計 \(S\) も更新します。
2 d
\(S \leq 0\) の場合
周期内を前から見て累積和を計算します。
初めて累積和が \(d\) 以上になった時刻を出力します。
最後まで見ても到達しなければ \(-1\) を出力します。
\(S > 0\) の場合
まず、1 周期内の累積和の最大値 \(M\) を求めます。
- \(d \leq M\) なら、最初の周期内で答えがある
- \(d > M\) なら、追い付ける直前の周期までまとめて飛ばす
飛ばす周期数を
\(q = \left\lceil \frac{d - M}{S} \right\rceil\)
とします。
整数での切り上げは
\(\left\lceil \frac{x}{S} \right\rceil = \frac{x + S - 1}{S}\)
で計算できます。
その後、周期内を前から見て、初めて
\(P_i \geq d - qS\)
となる \(i\) を探します。
答えは
\(qN + i\)
です。
計算量
- 時間計算量: \(O(NQ)\)
- 空間計算量: \(O(N)\)
制約で \(NQ \leq 10^7\) が保証されているため、各クエリで周期を \(O(N)\) 走査しても十分間に合います。
実装のポイント
直接持つべき値は速度 \(A_i, B_i\) ではなく、差分 \(C_i = B_i - A_i\) です。
更新クエリでは、\(C_i\) と周期合計 \(S\) を同時に更新します。
\(d\) は最大 \(10^{15}\)、速度差や累積も大きくなるため、64 bit 整数が必要です。Python では整数が任意精度なのでそのままで問題ありません。
\(C_i\) は負になることがあるため、「累積和が単調増加する」と仮定してはいけません。周期内は必ず前から順に確認します。
ソースコード
import sys
def main():
data = sys.stdin.buffer.read().split()
p = 0
N = int(data[p])
Q = int(data[p + 1])
p += 2
C = [0] * N
total = 0
for i in range(N):
a = int(data[p])
b = int(data[p + 1])
p += 2
v = b - a
C[i] = v
total += v
out = []
append = out.append
n = N
for _ in range(Q):
typ = data[p]
p += 1
if typ == b'1':
idx = int(data[p]) - 1
a = int(data[p + 1])
b = int(data[p + 2])
p += 3
nv = b - a
total += nv - C[idx]
C[idx] = nv
else:
d = int(data[p])
p += 1
if total <= 0:
cur = 0
ans = -1
i = 0
for v in C:
i += 1
cur += v
if cur >= d:
ans = i
break
append(str(ans))
else:
cur = 0
mx = 0
for v in C:
cur += v
if cur > mx:
mx = cur
diff = d - mx
if diff > 0:
q = (diff + total - 1) // total
target = d - q * total
base = q * n
else:
target = d
base = 0
cur = 0
i = 0
for v in C:
i += 1
cur += v
if cur >= target:
append(str(base + i))
break
sys.stdout.write("\n".join(out))
if __name__ == "__main__":
main()
この解説は gpt-5.5-high によって生成されました。
投稿日時:
最終更新: