C - 周期的な追いかけっこ / Periodic Chase 解説 by admin
Gemini 3.0 Flash (Thinking)概要
周期的に変化する2人の速さをもとに、高橋君が青木君に追い付く最小の整数時刻を求める問題です。クエリによって速さが更新されるため、効率的な再計算と追い付く判定が求められます。
考察
1. 相対速度に着目する
高橋君が座標 \(0\)、青木君が座標 \(d\) からスタートし、時刻 \(t\) において高橋君が青木君に追い付く条件は、「時刻 \(t\) までの高橋君の進んだ距離の合計」\(\ge\)「時刻 \(t\) までの青木君の進んだ距離の合計 \(+ d\)」です。
これを整理すると、各秒ごとの高橋君と青木君の速さの差（相対速度）を \(D_i = B_i - A_i\) としたとき、 $\(\sum_{s=1}^{t} D_{(s-1 \bmod N) + 1} \ge d\)\( を満たす最小の非負整数 \)t$ を探す問題に言い換えられます。
2. 周期性を利用する
時刻 \(t\) を \(N\) で割った商を \(q\)、余りを \(r\) とします（\(t = qN + r\)、ただし \(1 \le r \le N\)）。 \(1\) 周期（\(N\) 秒間）で縮まる距離を \(S_N = \sum_{i=1}^N D_i\)、周期の途中 \(r\) 秒までに縮まる距離を \(S_r = \sum_{i=1}^r D_i\) とすると、時刻 \(t\) までに縮まる合計距離は \(q \cdot S_N + S_r\) と表せます。
3. 追い付く条件の判定
クエリ 2 で与えられる \(d\) に対して、以下の 2 つのケースを考えます。
\(S_N \le 0\) の場合（1周期で距離が縮まない、または広がる） この場合、時間が経過しても周期ごとに状況が悪化するか変わらないため、最初の 1 周期（\(t=1\) から \(N\)）で追い付けなければ、その後も永遠に追い付けません。
\(S_N > 0\) の場合（1周期ごとに着実に距離が縮まる） この場合はいつか必ず追い付きます。各 \(r \in \{1, \dots, N\}\) について、 \(q \cdot S_N + S_r \ge d \iff q \cdot S_N \ge d - S_r\) を満たす最小の非負整数 \(q\) を求めます。
- \(d - S_r \le 0\) ならば \(q = 0\)
- \(d - S_r > 0\) ならば \(q = \lceil (d - S_r) / S_N \rceil\) こうして得られる \(t = qN + r\) の中で最小のものが答えとなります。
アルゴリズム
- 初期化:
- 各秒の相対速度 \(D_i = B_i - A_i\) を計算します。
- 累積和 \(S_r = \sum_{i=1}^r D_i\) を計算しておきます。
- クエリ 1 (更新):
- 指定された \(i\) 番目の \(A_i, B_i\) を更新し、\(D_i\) を再計算します。
- 累積和 \(S_k\) を \(k=i\) から \(N\) まで再計算します。これは \(O(N)\) で可能です。
- クエリ 2 (計算):
- \(S_N \le 0\) ならば、\(S_r \ge d\) となる最小の \(r \in \{1, \dots, N\}\) を探します。なければ \(-1\) です。
- \(S_N > 0\) ならば、各 \(r \in \{1, \dots, N\}\) に対して必要な周期数 \(q\) を計算し、最小の \(t = qN + r\) を求めます。これは \(O(N)\) で可能です。
計算量
- 時間計算量: \(O(NQ)\)
- 累積和の更新に \(O(N)\)、追い付く時刻の判定に \(O(N)\) かかります。
- 制約 \(NQ \le 10^7\) より、この計算量で十分に間に合います。
- 空間計算量: \(O(N)\)
- 速さや累積和を保持するための配列サイズは \(N\) に依存します。
実装のポイント
オーバーフローに注意: \(d\) が最大 \(10^{15}\) であり、移動距離も非常に大きくなるため、計算には 64bit 整数型（C++ の
long long）を使用してください。切り上げ除算: \(q = \lceil (d - S_r) / S_N \rceil\) の計算は、整数除算を用いて
(d - S_r + S_N - 1) / S_Nと書くことができます。入出力の高速化: クエリ数が多いため、
cin.tie(NULL); ios_base::sync_with_stdio(false);などで入出力を高速化しておくと安全です。ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/**
* Takahashi and Aoki chase each other on a number line.
* Speeds change periodically every N seconds.
* Takahashi catches Aoki if his position is greater than or equal to Aoki's at some integer time t.
* Let D_i = B_i - A_i be the relative gain Takahashi makes in the i-th second of the cycle.
* The total gain at time t = qN + r (0 <= r < N) is q * S_N + S_r, where S_k is the prefix sum of D_i.
*/
int main() {
// Speed up standard I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, Q;
if (!(cin >> N >> Q)) return 0;
// Use long long for all speed and distance calculations to prevent overflow.
// Coordinates can reach around 3 * 10^18, which fits in a 64-bit signed integer.
vector<long long> A(N + 1), B(N + 1), D(N + 1), S(N + 1, 0);
for (int i = 1; i <= N; ++i) {
cin >> A[i] >> B[i];
D[i] = B[i] - A[i];
}
// Precompute the gain at each second within the first cycle.
for (int i = 1; i <= N; ++i) {
S[i] = S[i - 1] + D[i];
}
while (Q--) {
int type;
cin >> type;
if (type == 1) {
// Update speed and prefix sums for the modified table entry.
int i;
long long a, b;
cin >> i >> a >> b;
A[i] = a;
B[i] = b;
D[i] = B[i] - A[i];
// Re-calculate prefix sums from index i to N. Complexity: O(N).
for (int k = i; k <= N; ++k) {
S[k] = S[k - 1] + D[k];
}
} else if (type == 2) {
long long d;
cin >> d;
long long SN = S[N];
// If the total gain per cycle is non-positive, Takahashi must catch Aoki
// in the first cycle because the gain will not increase in subsequent cycles.
if (SN <= 0) {
long long ans = -1;
for (int r = 1; r <= N; ++r) {
if (S[r] >= d) {
ans = r;
break;
}
}
cout << ans << "\n";
} else {
// If the gain per cycle is positive, Takahashi will always catch Aoki eventually.
// We iterate through all possible remainders r (1 to N) to find the minimum t = qN + r.
// Complexity: O(N).
long long min_t = -1;
for (int r = 1; r <= N; ++r) {
long long qr = 0;
if (d > S[r]) {
// Calculate the minimum number of full cycles needed to close the gap.
// q_r * SN + S_r >= d => q_r * SN >= d - S_r => q_r >= ceil((d - S_r) / SN)
qr = (d - S[r] + SN - 1) / SN;
}
long long tr = qr * N + r;
if (min_t == -1 || tr < min_t) {
min_t = tr;
}
}
cout << min_t << "\n";
}
}
}
return 0;
}
この解説は gemini-3-flash-thinking によって生成されました。