概要

位置と速度が与えられた \(N\) 人のランナーについて、レース中に発生する「追い抜き」の総回数を求める問題です。これは転倒数（inversion count）を求める問題に帰着できます。

考察

追い抜きが発生する条件

ランナー \(i\) がランナー \(j\) を追い抜くには、以下の2つの条件を同時に満たす必要があります：

1. 時刻 \(0\) でランナー \(i\) がランナー \(j\) より後方にいる：\(P_i < P_j\)
2. ある時刻 \(t > 0\) でランナー \(i\) がランナー \(j\) より前方になる

2番目の条件を数式で表すと： $\(P_i + V_i \times t > P_j + V_j \times t\)\( \)\(V_i \times t - V_j \times t > P_j - P_i\)\( \)\((V_i - V_j) \times t > P_j - P_i\)$

\(P_j - P_i > 0\)（条件1より）なので、この不等式を満たす正の時刻 \(t\) が存在するためには \(V_i > V_j\) が必要です。

問題の言い換え

結局、追い抜きが発生するペア \((i, j)\) の条件は： - \(P_i < P_j\)（\(i\) が後方）かつ \(V_i > V_j\)（\(i\) が速い）

つまり、位置の順序と速度の順序が逆転しているペアの数を数えればよいです。

素朴なアプローチの問題点

全てのペア \((i, j)\) を調べると \(O(N^2)\) となり、\(N = 2 \times 10^5\) では間に合いません（約 \(4 \times 10^{10}\) 回の計算が必要）。

転倒数への帰着

ランナーを位置 \(P\) の昇順にソートします。ソート後の速度の列を \(V_1', V_2', \ldots, V_N'\) とすると： - インデックス \(i < j\) は「\(i\) 番目のランナーの方が後方にいた」ことを意味 - \(V_i' > V_j'\) は「後方のランナーの方が速い」ことを意味

したがって、速度列の転倒数（\(i < j\) かつ \(V_i' > V_j'\) となるペアの数）が答えになります。

アルゴリズム

マージソートを用いた転倒数のカウントを使用します。

1. ランナーを初期位置 \(P\) の昇順にソートする
2. ソート後の速度列を取り出す
3. 速度列に対してマージソートを行いながら転倒数を数える

マージソートで転倒数を数える仕組み： - 配列を左右に分割し、それぞれを再帰的にソート - マージ時、右側の要素を先に選ぶ場合（右側の要素 < 左側の残り要素）、左側に残っている全要素との間に転倒が存在 - よって、右側から要素を選ぶたびに「左側の残り要素数」を転倒数に加算

具体例

位置と速度が以下の3人の場合： - ランナーA: 位置=10, 速度=5 - ランナーB: 位置=5, 速度=8
- ランナーC: 位置=15, 速度=3

位置でソート後：B(5), A(10), C(15) 速度列：[8, 5, 3]

転倒数：(8,5), (8,3), (5,3) の3つ → 答えは3回

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • マージソートによる転倒数カウントに \(O(N \log N)\)
• 空間計算量: \(O(N)\)
  • ランナー情報の格納とマージソートの作業領域

実装のポイント

• マージソートの実装では、右側の要素を選ぶときに len(left) - i（左側の残り要素数）を転倒数に加算する

• 安定ソートである必要はないが、同じ値がないことが保証されているので問題なし

• Python では再帰の深さに注意が必要だが、\(N \leq 2 \times 10^5\) で再帰深さは約 \(\log_2 N \approx 18\) なので問題なし

  ソースコード

import sys

def merge_sort_count(arr):
    if len(arr) <= 1:
        return arr, 0
    
    mid = len(arr) // 2
    left, left_inv = merge_sort_count(arr[:mid])
    right, right_inv = merge_sort_count(arr[mid:])
    
    merged = []
    inversions = left_inv + right_inv
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            inversions += len(left) - i
            j += 1
    
    merged.extend(left[i:])
    merged.extend(right[j:])
    
    return merged, inversions

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx])
    idx += 1
    
    runners = []
    for i in range(N):
        P = int(input_data[idx])
        V = int(input_data[idx + 1])
        idx += 2
        runners.append((P, V))
    
    # Sort by initial position (descending) - runner in front first
    # For runner i to overtake runner j:
    # - At time 0: P_i < P_j (i is behind j)
    # - At some time t > 0: P_i + V_i * t > P_j + V_j * t
    # This means V_i > V_j (i is faster than j)
    
    # So we need to count pairs (i, j) where P_i < P_j and V_i > V_j
    # This is counting inversions when we sort by position and look at velocities
    
    # Sort runners by position in ascending order
    runners.sort(key=lambda x: x[0])
    
    # Extract velocities in order of increasing position
    velocities = [v for p, v in runners]
    
    # Count inversions in velocities array
    # An inversion (i, j) where i < j and velocities[i] > velocities[j]
    # means: runner at position i (smaller position) has higher velocity
    # So runner at smaller position will overtake runner at larger position
    
    _, count = merge_sort_count(velocities)
    
    print(count)

solve()

---

この解説は claude4.5opus によって生成されました。