E - 直線コースの追い越し / Overtaking on a Straight Course 解説 by admin
gpt-5.5-high概要
二人の位置 \(f(t), g(t)\) は、走っている間は直線的に増え、給水中は一定になる 折れ線関数 です。
差 \(h(t)=f(t)-g(t)\) の符号が変わる回数を数えれば、追い越し回数が分かります。
考察
二人の位置は常に連続ですが、速度は以下のタイミングでだけ変化します。
- 給水所に到着したとき
- 給水を終えて再出発したとき
つまり、これらの「イベント時刻」の間では、二人の速度はそれぞれ一定です。
したがって、その区間では
\[ h(t)=f(t)-g(t) \]
も一次関数になります。
一次関数の符号変化は、区間の両端の符号を見るだけで判定できます。
例えば、ある区間の左端と右端での \(h(t)\) の符号が
- \(+\), \(+\) なら符号変化なし
- \(-\), \(-\) なら符号変化なし
- \(+\), \(-\) なら区間内で 1 回符号変化
- \(-\), \(+\) なら区間内で 1 回符号変化
です。
また、\(h(t)=0\) になる時刻や区間の扱いに注意が必要です。
例えば符号列が
\[ + \to 0 \to - \]
なら追い越しは 1 回ですが、
\[ + \to 0 \to + \]
なら追い越しではありません。
そのため、時間順に見たときの 直前の非 0 の符号 を覚えておき、次に現れた非 0 の符号が違っていたら追い越し 1 回、と考えます。
時刻 \(0\) では二人は同じ位置にいますが、これは追い越しに数えません。
したがって、最初の非 0 符号が現れても回数は増やしません。
また、観測終了時刻 \(T\) ちょうどで符号が変わる場合も数えません。
これは、区間の右端が \(T\) で \(h(T)=0\) の場合、次の符号を見ないことで自然に処理できます。
アルゴリズム
まず、各走者についてイベントを時刻順に管理します。
速度を \(u\)、待ち時間列を \(A_i\) とします。
給水所 \(i\) への到着時刻は
\[ \frac{i}{u}+\sum_{j=1}^{i-1} A_j \]
です。
給水所 \(i\) からの出発時刻は、\(i<N\) のとき
\[ \frac{i}{u}+\sum_{j=1}^{i} A_j \]
です。
ゴールである給水所 \(N\) では停止しないので、出発イベントはありません。
各時刻区間では、走者の位置は次のどちらかの形で表せます。
- 走行中：
\[ x(t)=u t - uP \]
ここで \(P\) はそれまでに給水で停止した合計時間です。
- 停止中：
\[ x(t)=i \]
ここで \(i\) は停止している給水所番号です。
つまり、各走者の位置は常に
\[ x(t)=at+b \]
という一次式で表せます。
処理手順は次の通りです。
- 高橋君と青木君それぞれについて、次のイベント時刻を持つ。
- 現在時刻を
curとする。 - 次に起こるイベント時刻を
nxtとする。- ただし、観測終了時刻 \(T\) を超える場合は
nxt = Tとする。
- ただし、観測終了時刻 \(T\) を超える場合は
- 区間 \([cur, nxt]\) では、両者の位置は一次式なので、\(h(t)=f(t)-g(t)\) も一次式。
- \(h(cur)\) と \(h(nxt)\) の符号を調べる。
- 非 0 の符号列を更新し、直前の非 0 符号と異なれば答えを \(1\) 増やす。
cur = nxtとして、その時刻に起こるイベントをすべて処理する。cur < Tの間繰り返す。
符号の更新は次のように考えます。
- 両端がともに \(0\)：何もしない
- 左端だけ \(0\)：右端の符号を使う
- 右端だけ \(0\)：左端の符号を使う
- 両端が同じ非 0 符号：その符号を使う
- 両端が異なる非 0 符号：左端の符号、右端の符号を順に使う
これにより、区間内の符号変化も、イベント時刻での符号変化も正しく数えられます。
観測終了時刻 \(T\) は、二人のうち遅い方がゴールに到着する時刻です。
高橋君のゴール時刻は
\[ \sum_{i=1}^{N-1} R_i + \frac{N}{V} \]
青木君のゴール時刻は
\[ \sum_{i=1}^{N-1} S_i + \frac{N}{W} \]
なので、
\[ T=\max\left( \sum_{i=1}^{N-1} R_i + \frac{N}{V}, \sum_{i=1}^{N-1} S_i + \frac{N}{W} \right) \]
です。
\(R_N, S_N\) はゴール後の停止なので使いません。
計算量
各走者のイベント数は、到着が \(N\) 回、出発が \(N-1\) 回なので \(O(N)\) 個です。
それらを時刻順にマージしながら処理します。
- 時間計算量: \(O(N)\)
- 空間計算量: \(O(N)\)
実装のポイント
時刻には \(\frac{i}{V}\) や \(\frac{i}{W}\) が現れるため、小数になります。
浮動小数点数を使うと、ちょうど同じ位置になる場合や、時刻 \(T\) ちょうどの判定で誤差が出る可能性があります。
そのため、時刻は分数
\[ \frac{\text{num}}{\text{den}} \]
として管理します。
時刻の比較は、
\[ \frac{a}{b} < \frac{c}{d} \]
を
\[ ad < cb \]
で判定します。
また、値が非常に大きくなるため、long long では足りません。
実装では __int128_t を使ってオーバーフローを防いでいます。
さらに、待ち時間が \(0\) の場合、到着イベントと出発イベントが同じ時刻に起こります。
そのため、ある時刻に発生するイベントは while などですべてまとめて処理する必要があります。
ソースコード
#include <bits/stdc++.h>
using namespace std;
using i128 = __int128_t;
struct Time {
i128 num;
long long den;
bool inf;
};
int cmpTime(const Time& a, const Time& b) {
if (a.inf && b.inf) return 0;
if (a.inf) return 1;
if (b.inf) return -1;
i128 lhs = a.num * (i128)b.den;
i128 rhs = b.num * (i128)a.den;
if (lhs < rhs) return -1;
if (lhs > rhs) return 1;
return 0;
}
Time minTime(const Time& a, const Time& b) {
return cmpTime(a, b) <= 0 ? a : b;
}
struct Runner {
int N;
long long speed;
const vector<long long>* wait;
bool hasEvent;
int type; // 0: arrival, 1: departure
int station;
i128 nextNum;
i128 prefixWait;
long long slope;
i128 intercept;
Runner(int n, long long sp, const vector<long long>& w)
: N(n), speed(sp), wait(&w) {
hasEvent = true;
type = 0;
station = 1;
nextNum = 1;
prefixWait = 0;
slope = speed;
intercept = 0;
}
Time nextTime() const {
if (!hasEvent) return {0, 1, true};
return {nextNum, speed, false};
}
void process(const Time& cur) {
while (hasEvent) {
i128 lhs = nextNum * (i128)cur.den;
i128 rhs = cur.num * (i128)speed;
if (lhs != rhs) break;
if (type == 0) {
int i = station;
slope = 0;
intercept = i;
if (i == N) {
hasEvent = false;
} else {
type = 1;
station = i;
nextNum += (i128)(*wait)[i - 1] * speed;
}
} else {
int i = station;
prefixWait += (*wait)[i - 1];
slope = speed;
intercept = -prefixWait * speed;
type = 0;
station = i + 1;
nextNum += 1;
}
}
}
};
int signAt(const Runner& t, const Runner& a, const Time& x) {
i128 val = ((i128)t.slope - (i128)a.slope) * x.num
+ (t.intercept - a.intercept) * (i128)x.den;
if (val > 0) return 1;
if (val < 0) return -1;
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
long long V, W;
cin >> N >> V >> W;
vector<long long> R(N), S(N);
for (int i = 0; i < N; i++) cin >> R[i];
for (int i = 0; i < N; i++) cin >> S[i];
i128 sumR = 0, sumS = 0;
for (int i = 0; i < N - 1; i++) {
sumR += R[i];
sumS += S[i];
}
Time finishT = {sumR * V + N, V, false};
Time finishA = {sumS * W + N, W, false};
Time Tobs = cmpTime(finishT, finishA) >= 0 ? finishT : finishA;
Runner tak(N, V, R);
Runner aok(N, W, S);
Time cur = {0, 1, false};
long long ans = 0;
int lastSign = 0;
auto feed = [&](int s) {
if (s == 0) return;
if (lastSign != 0 && lastSign != s) ans++;
lastSign = s;
};
auto addInterval = [&](int l, int r) {
if (l == 0 && r == 0) return;
if (l == 0) {
feed(r);
} else if (r == 0) {
feed(l);
} else if (l == r) {
feed(l);
} else {
feed(l);
feed(r);
}
};
tak.process(cur);
aok.process(cur);
while (cmpTime(cur, Tobs) < 0) {
Time nxt = minTime(tak.nextTime(), aok.nextTime());
if (cmpTime(nxt, Tobs) > 0) nxt = Tobs;
if (cmpTime(nxt, cur) == 0) {
tak.process(cur);
aok.process(cur);
continue;
}
int sl = signAt(tak, aok, cur);
int sr = signAt(tak, aok, nxt);
addInterval(sl, sr);
cur = nxt;
tak.process(cur);
aok.process(cur);
}
cout << ans << '\n';
return 0;
}
この解説は gpt-5.5-high によって生成されました。