概要

二人の位置差 \(f(t)-g(t)\) の符号が何回変わるかを数える問題です。
給水所への到着・停止終了など、速度が変わる時刻だけをイベントとしてシミュレーションします。

考察

二人の位置は時間に対して連続で、各区間では一定速度で動くため、位置差 \(f(t)-g(t)\) は「区分的な一次関数」になります。
したがって、速度が変わらない区間では符号変化は高々 \(1\) 回しか起こりません。

素朴な方法の問題点

実時間をそのまま扱うと、給水所間の移動時間は

• 高橋君: \(\frac{1}{V}\) 秒
• 青木君: \(\frac{1}{W}\) 秒

となり、分数が大量に出てきます。
浮動小数点数で扱うと誤差により、ちょうど同じ位置になる場合や、ゴール時刻ちょうどでの判定を誤る可能性があります。

また、時刻を細かく刻んでシミュレーションすることは、停止時間が最大 \(10^9\) 秒、\(N\) も最大 \(5 \times 10^5\) なので不可能です。

時刻を整数にスケールする

そこで、時刻を \(L = VW\) 倍して扱います。

実時刻 \(t\) に対して、スケール後の時刻を

\[ \tau = Lt \]

とします。

このとき、給水所間の距離 \(1\) を進むのにかかるスケール後の時間は、

• 高橋君: \(\frac{1}{V} \times VW = W\)
• 青木君: \(\frac{1}{W} \times VW = V\)

となり、すべて整数になります。

また、\(x\) 秒の停止時間はスケール後では

\[ x \times VW \]

です。

これにより、全てのイベント時刻を整数で管理できます。

位置差も整数で管理する

位置差そのものではなく、

\[ H(\tau) = L(f(t)-g(t)) \]

を考えます。

\(L\) は正なので、\(H(\tau)\) の符号は \(f(t)-g(t)\) の符号と同じです。

さらに、スケール後の時刻 \(\tau\) に対する \(H\) の傾きは、

• 高橋君が走っているなら \(+V\)、止まっているなら \(0\)
• 青木君が走っているなら \(-W\)、止まっているなら \(0\)

となります。

つまり、ある区間での \(H\) の変化量は

\[ (\text{高橋君の速度} - \text{青木君の速度}) \times \Delta \tau \]

で計算できます。

アルゴリズム

まず、二人のゴール到着時刻をスケール後の時刻で計算します。

高橋君のゴール到着時刻は

\[ NW + L\sum_{i=1}^{N-1} R_i \]

青木君のゴール到着時刻は

\[ NV + L\sum_{i=1}^{N-1} S_i \]

です。

ゴールである給水所 \(N\) では停止しないため、\(R_N, S_N\) は加えません。

観測終了時刻はこの大きい方です。

\[ T_{\text{end}} = \max(\text{高橋君の到着時刻}, \text{青木君の到着時刻}) \]

次に、各走者について以下を管理します。

• 現在走っているか止まっているか
• 次に状態が変わる時刻
• すでに到着した給水所の番号

状態が変わるイベントは以下です。

• 給水所に到着する
• 停止が終わって再び走り始める
• ゴールに到着する

現在時刻を cur、次のイベント時刻を nxt とします。
区間 \([cur, nxt]\) では二人の速度は変わらないので、\(H\) は一次関数です。

この区間の始点と終点での値をそれぞれ \(h, h_1\) とすると、

\[ h_1 = h + (\text{高橋君の現在速度} - \text{青木君の現在速度}) \times (nxt-cur) \]

です。

符号変化の数え方

追い越しは、\(H\) の符号が正から負、または負から正に変わったときに発生します。

ただし、\(H=0\) がしばらく続く場合もあるため、単純に隣り合う時刻の符号を見るだけでは不十分です。

そこで、直前に現れた \(0\) でない符号を prev として持ちます。

• prev = 1: 直前は高橋君が前
• prev = -1: 直前は青木君が前
• prev = 0: まだ前後関係が確定していない

ある区間で新しく現れた \(0\) でない符号が prev と異なれば、追い越しが \(1\) 回起きたことになります。

例えば、

正 → 0 が続く → 負

の場合、符号は正から負に変わったので追い越し \(1\) 回です。

一方、

正 → 0 が続く → 正

の場合、前後関係は入れ替わっていないので追い越しではありません。

また、時刻 \(0\) では二人は同じ位置にいますが、出発直後に一方が前に出ることは追い越しと数えないため、最初は prev = 0 とします。

区間内での処理

区間内で \(H\) は一次関数なので、符号の現れ方は限られています。

• \(h = 0\), \(h_1 \neq 0\)
  区間の途中から符号 sign(h1) が現れる
• \(h \neq 0\), \(h_1 = 0\)
  区間の終わりまでは符号 sign(h) が続く
• \(h, h_1\) が同符号
  その符号が続く
• \(h, h_1\) が異符号
  区間内で一度 \(0\) を通過するので、追い越しが \(1\) 回起こる

これをイベントごとに繰り返せば、全体の追い越し回数が求められます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

各走者について、各給水所への到着と停止終了を高々一度ずつ処理するだけなので、イベント数は \(O(N)\) です。

実装のポイント

• 浮動小数点数は使わず、時刻を \(VW\) 倍してすべて整数で扱います。

• ゴールである給水所 \(N\) では停止しないため、\(R_N, S_N\) は無視します。

• 時刻 \(T_{\text{end}}\) ちょうどで符号が変わる場合は、追い越しとして数えません。

• 同時刻に二人のイベントが起きる場合があるので、同じ cur にあるイベントは両方処理します。

• 値が非常に大きくなるため、Python では問題ありませんが、C++ などでは long long を超える可能性があり、__int128 などが必要です。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline

    N, V, W = map(int, input().split())
    R = list(map(int, input().split()))
    S = list(map(int, input().split()))

    L = V * W

    finish_t = (sum(R) - R[-1]) * L + N * W
    finish_a = (sum(S) - S[-1]) * L + N * V
    T_end = finish_t if finish_t >= finish_a else finish_a
    INF = T_end + 1

    cur = 0
    h = 0
    ans = 0
    prev = 0

    k_t = 0
    k_a = 0

    vel_t = V
    vel_a = W

    step_t = W
    step_a = V

    next_t = step_t
    next_a = step_a

    while cur < T_end:
        nxt = next_t if next_t < next_a else next_a
        if nxt > T_end:
            nxt = T_end

        dt = nxt - cur
        slope = vel_t - vel_a
        h1 = h + slope * dt if slope else h

        if h == 0:
            if h1 != 0:
                sgn = 1 if h1 > 0 else -1
                if prev != 0 and prev != sgn:
                    ans += 1
                prev = sgn
        elif h1 == 0:
            sgn = 1 if h > 0 else -1
            if prev != 0 and prev != sgn:
                ans += 1
            prev = sgn
        else:
            s0 = 1 if h > 0 else -1
            s1 = 1 if h1 > 0 else -1
            if s0 == s1:
                if prev != 0 and prev != s0:
                    ans += 1
                prev = s0
            else:
                if prev != 0 and prev != s0:
                    ans += 1
                ans += 1
                prev = s1

        h = h1
        cur = nxt

        if cur == T_end:
            break

        if next_t == cur:
            if vel_t:
                k_t += 1
                if k_t == N:
                    vel_t = 0
                    next_t = INF
                else:
                    r = R[k_t - 1]
                    if r:
                        vel_t = 0
                        next_t = cur + r * L
                    else:
                        next_t = cur + step_t
            else:
                vel_t = V
                next_t = cur + step_t

        if next_a == cur:
            if vel_a:
                k_a += 1
                if k_a == N:
                    vel_a = 0
                    next_a = INF
                else:
                    s = S[k_a - 1]
                    if s:
                        vel_a = 0
                        next_a = cur + s * L
                    else:
                        next_a = cur + step_a
            else:
                vel_a = W
                next_a = cur + step_a

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。