概要

高橋君と青木君がそれぞれ異なる一定の速さで走り、給水所で異なる時間だけ立ち止まりながら直線コースを進むとき、二人の間で発生する「追い越し」の合計回数を求める問題です。各給水所への到着時刻と出発時刻を求め、各区間および各給水所での前後関係の入れ替わりを判定することで、全体の追い越し回数を \(O(N)\) で計算します。

考察

1. 小数の排除（時間スケールの変換）

高橋君の速さは \(V\)、青木君の速さは \(W\) です。距離 \(1\) を進むのにかかる時間は、高橋君が \(\frac{1}{V}\) 秒、青木君が \(\frac{1}{W}\) 秒となり、そのまま計算すると小数の誤差が発生します。 これを避けるために、時間の単位をすべて \(V \times W\) 倍します。これにより、すべての時間を整数として扱うことができます。 - 距離 \(1\) を進むのにかかる時間：高橋君は \(W\)、青木君は \(V\) - 給水所 \(i\) での停止時間：高橋君は \(R_i \times V \times W\)、青木君は \(S_i \times V \times W\)

※ \(V, W, R_i \le 10^9\) であるため、掛け算の結果は最大で \(10^{27}\) 程度に達します。標準的な 64 ビット整数（long long）ではオーバーフローするため、C++の 128 ビット整数（__int128_t）を使用する必要があります。

2. 追い越しが発生する場所の分類

追い越しが発生するタイミングは、以下の 2 つのケースに大別できます。

ケース A: 給水所 \(i-1\) から 給水所 \(i\) への移動中（開区間 \((i-1, i)\)）

二人は移動中、それぞれ一定の速さで走ります。したがって、この区間内で発生する追い越しは高々 \(1\) 回です。 給水所 \(i-1\) を出発した直後の前後関係と、給水所 \(i\) に到着した直前の前後関係が逆転している場合、移動中にちょうど \(1\) 回の追い越しが発生します。

ケース B: 給水所 \(i\) での滞在中（給水所 \(i\) 上）

一方が給水所で休んでいる間にもう一方が追いつき、追い越していくケースです。 これが起こるためには、以下の 2 つの条件を両方満たす必要があります。 1. 滞在時間の重複: 二人が同時に給水所 \(i\) に滞在している時間帯が一時でも存在する。 2. 前後関係の逆転: 給水所 \(i\) に到着した時点の前後関係と、給水所 \(i\) を出発した時点の前後関係が異なる。

---

アルゴリズム

ステップ 1: 到着時刻・出発時刻の計算

高橋君の給水所 \(i\) への到着時刻を \(a_i\)、出発時刻を \(a'_i\) とします。青木君についても同様に \(b_i, b'_i\) とします。 これらは以下の漸化式で \(i = 1\) から \(N\) まで順に求められます（初期値は \(a_0 = a'_0 = b_0 = b'_0 = 0\)）。

• 高橋君:
  • \(a_i = a'_{i-1} + W\)
  • \(a'_i = a_i + R_i \times V \times W\) （ただし、ゴールである \(i=N\) では \(a'_N = a_N\)）
• 青木君:
  • \(b_i = b'_{i-1} + V\)
  • \(b'_i = b_i + S_i \times V \times W\) （ただし、ゴールである \(i=N\) では \(b'_N = b_N\)）

ステップ 2: 前後関係の追跡と追い越し判定

現在の前後関係を表す変数 current_sign を用意します（高橋君が前にいれば \(+1\)、青木君が前にいれば \(-1\)）。 スタート直後は速い方が前に出るため、 \(V > W\) なら \(+1\)、そうでなければ \(-1\) で初期化します。

各 \(i = 1, 2, \ldots, N\) について、以下の判定を行います。

1. 移動中の追い越し判定

給水所 \(i-1\) を出発した直後の位置関係（出発時刻の差 \(b'_{i-1} - a'_{i-1}\) の符号）と、給水所 \(i\) に到着した時点の位置関係（到着時刻の差 \(b_i - a_i\) の符号）を比較します。 もしこれら二つの符号が異なっていれば、移動中に追い越しが発生したと判定し、答えを \(1\) 増やして current_sign の符号を反転させます。

2. 給水所 \(i\) での追い越し判定（\(i < N\) の場合のみ）

給水所 \(i\) への到着時の前後関係 \(S_{in}\) と、出発時の前後関係 \(S_{out}\) を定義します。 - 到着時 \(S_{in}\): - 先に到着した（到着時刻が早い）方が前になります。同時に到着した場合は、直前の移動中の前後関係 current_sign を引き継ぎます。 - 出発時 \(S_{out}\): - 先に出発した（出発時刻が早い）方が前になります。同時に出発した場合は、出発直後に速い方が前に出るため、 \(V > W\) なら高橋君が前（\(+1\)）、そうでなければ青木君が前（\(-1\)）になります。

二人の給水所 \(i\) での滞在期間 \([a_i, a'_i]\) と \([b_i, b'_i]\) が重複しており（条件：\(a_i \le b'_i\) かつ \(b_i \le a'_i\)）、かつ \(S_{in} \neq S_{out}\) であれば、給水所で追い越しが発生したと判定し、答えを \(1\) 増やします。 その後、current_sign を \(S_{out}\) に更新して次のステップへ進みます。

---

計算量

• 時間計算量: \(O(N)\)
  • \(1\) から \(N\) までのループを \(1\) 回回すだけであり、各ループ内の処理はすべて \(O(1)\) の算術演算のみで完結するため、全体で \(O(N)\) 時間で動作します。
• 空間計算量: \(O(N)\)
  • 各給水所における到着時刻・出発時刻を記録する配列（サイズ \(N+1\)）をいくつか保持するため、空間計算量は \(O(N)\) となります。

---

実装のポイント

• 128ビット整数の利用: C++ の __int128_t を使用して、時間スケール変換時のオーバーフローを防いでいます。__int128_t は標準の std::cin や std::cout で直接入出力できないため、入力の段階では long long で受け取り、計算の過程で __int128_t にキャストしています。

• ゴールの例外処理: 問題文の指示通り、ゴール（給水所 \(N\)）では給水のための停止を行いません（\(R_N = S_N = 0\) と同等）。また、ゴールに到着した瞬間の追い越しはカウントしないため、給水所 \(N\) での滞在中の追い越し判定は行わないようにループの条件を調整しています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

using int128 = __int128_t;

int main() {
    // Optimize standard I/O operations for performance
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long V, W;
    if (!(cin >> N >> V >> W)) return 0;

    vector<long long> R(N + 1), S(N + 1);
    for (int i = 1; i <= N; ++i) cin >> R[i];
    for (int i = 1; i <= N; ++i) cin >> S[i];

    // a[i] and b[i] store the arrival times at station i (scaled by V * W)
    // a_prime[i] and b_prime[i] store the departure times from station i (scaled by V * W)
    vector<int128> a(N + 1), a_prime(N + 1);
    vector<int128> b(N + 1), b_prime(N + 1);

    a[0] = 0; a_prime[0] = 0;
    b[0] = 0; b_prime[0] = 0;

    int128 VW = (int128)V * W;

    for (int i = 1; i <= N; ++i) {
        a[i] = a_prime[i-1] + W;
        if (i < N) {
            a_prime[i] = a[i] + (int128)R[i] * VW;
        } else {
            a_prime[i] = a[i]; // No stopping at the goal
        }

        b[i] = b_prime[i-1] + V;
        if (i < N) {
            b_prime[i] = b[i] + (int128)S[i] * VW;
        } else {
            b_prime[i] = b[i]; // No stopping at the goal
        }
    }

    long long ans = 0;
    // current_sign: +1 if Takahashi is ahead, -1 if Aoki is ahead
    int current_sign = (V > W) ? 1 : -1;

    for (int i = 1; i <= N; ++i) {
        // 1. Check for overtaking inside the open interval (i-1, i)
        int128 R_prev = b_prime[i-1] - a_prime[i-1];
        int128 L_curr = b[i] - a[i];
        if ((R_prev > 0 && L_curr < 0) || (R_prev < 0 && L_curr > 0)) {
            ans++;
            current_sign = -current_sign;
        }

        // 2. Check for overtaking at water station i
        if (i < N) {
            int S_in = 0;
            if (L_curr > 0) S_in = 1;
            else if (L_curr < 0) S_in = -1;
            else S_in = current_sign;

            int128 R_curr = b_prime[i] - a_prime[i];
            int S_out = 0;
            if (R_curr > 0) S_out = 1;
            else if (R_curr < 0) S_out = -1;
            else S_out = (V > W) ? 1 : -1;

            // Check if their resting intervals at station i overlap
            if (a[i] <= b_prime[i] && b[i] <= a_prime[i]) {
                if (S_in != S_out) {
                    ans++;
                }
            }
            current_sign = S_out;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。