概要

二人の位置 \(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 \]

という一次式で表せます。

処理手順は次の通りです。

1. 高橋君と青木君それぞれについて、次のイベント時刻を持つ。
2. 現在時刻を cur とする。
3. 次に起こるイベント時刻を nxt とする。
   • ただし、観測終了時刻 \(T\) を超える場合は nxt = T とする。
4. 区間 \([cur, nxt]\) では、両者の位置は一次式なので、\(h(t)=f(t)-g(t)\) も一次式。
5. \(h(cur)\) と \(h(nxt)\) の符号を調べる。
6. 非 0 の符号列を更新し、直前の非 0 符号と異なれば答えを \(1\) 増やす。
7. cur = nxt として、その時刻に起こるイベントをすべて処理する。
8. 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 によって生成されました。