概要

\(N\) 人のランナーの初期位置 \(P_i\) と速度 \(V_i\) が与えられたとき、将来的に発生する「追い抜き」の総回数を求める問題です。追い抜きは、初期状態で後ろにいるランナーが、自分より前にいるランナーよりも速い場合にのみ発生します。

考察

追い抜きが発生する条件

ある 2 人のランナー \(i\) と \(j\) について、時刻 \(0\) でランナー \(i\) がランナー \(j\) より後ろにいる（\(P_i < P_j\)）とします。 このとき、ある時刻 \(t > 0\) でランナー \(i\) がランナー \(j\) を追い抜くための条件は、ランナー \(i\) の速度がランナー \(j\) の速度よりも大きいこと、すなわち \(V_i > V_j\) であることです。

もし \(V_i < V_j\) であれば、時間の経過とともに 2 人の距離は離れていくため、追い抜きは決して発生しません。

問題の言い換え

すべてのランナーを初期位置 \(P_i\) の昇順（小さい順）に並べ替えてみましょう。 このとき、追い抜き回数を数えることは、並べ替えた後の速度の列において、「自分より左側（初期位置が手前）にあるのに、自分より値が大きい（速度が速い）要素」の数を数えることと同じになります。

これは、アルゴリズムの分野で「転倒数（Inversion Number）」と呼ばれる有名な問題に帰着されます。

素直な解法と課題

すべてのペア \((i, j)\) について追い抜きが起きるか判定すると、計算量は \(O(N^2)\) となります。今回の制約は \(N \le 2 \times 10^5\) であるため、これでは制限時間内に計算が終わりません。より効率的な \(O(N \log N)\) のアルゴリズムが必要です。

アルゴリズム

以下の手順で解を求めます。

1. ソート: ランナーを初期位置 \(P_i\) の昇順でソートします。
2. 座標圧縮: 速度 \(V_i\) の値は最大 \(10^9\) と非常に大きいため、そのままでは配列の添字として使えません。速度の大小関係だけが重要なので、速度を \(1\) から \(N\) までの順位に変換（座標圧縮）します。
3. 転倒数の計算: Binary Indexed Tree (BIT) またはセグメント木を用いて、ソートされた速度の列を左から順に処理しながら転倒数をカウントします。
   • 現在のランナーの速度の順位を \(r\) とします。
   • これまでに処理した（自分より初期位置が小さい）ランナーのうち、速度の順位が \(r\) より大きいものの個数を BIT を使って求め、答えに加算します。
   • BIT に現在の速度 \(r\) を登録します。

計算量

• 時間計算量: \(O(N \log N)\)
  • ランナーのソートに \(O(N \log N)\)
  • 速度の座標圧縮に \(O(N \log N)\)
  • BIT を用いた転倒数の計算に \(O(N \log N)\) かかります。
• 空間計算量: \(O(N)\)
  • ランナーのデータや BIT の管理に \(N\) に比例したメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと高速です。

• 転倒数のカウント: BIT で「\(r\) より大きいものの個数」を求める際は、「全体の個数 - \(r\) 以下の個数」として計算するのが一般的です。

• 座標圧縮の辞書: rank_map = {v: i + 1 for i, v in enumerate(v_sorted)} のように辞書（ハッシュマップ）を使うことで、各速度の順位を \(O(1)\) で引けるようになります。

  ソースコード

import sys

def solve():
    # 高速な入出力のために、すべての入力を一度に読み込み、空白で分割してリスト化します。
    # sys.stdin.read().split() は、空白、タブ、改行をすべて区切り文字として扱います。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 最初のエントリはランナーの人数 N です。
    N = int(input_data[0])
    if N == 0:
        print(0)
        return
    
    # P_i と V_i を効率的にパースしてペアにします。
    # input_data[1:2*N+1:2] は P_1, P_2, ..., P_N を抽出し、
    # input_data[2:2*N+1:2] は V_1, V_2, ..., V_N を抽出します。
    # map(int, ...) で整数に変換し、zip で (位置, 速度) のタプルのリストを作成します。
    runners = list(zip(map(int, input_data[1:2*N+1:2]), map(int, input_data[2:2*N+1:2])))
    
    # ランナーを初期位置 P_i の昇順でソートします。
    # すべての P_i は異なるため、一意な順序が得られます。
    runners.sort()
    
    # 位置の順にソートされた状態での速度のリストを抽出します。
    # 追い抜き回数を求めることは、この速度のリストにおける「転倒数」を求めることと同義です。
    # なぜなら、P_i < P_j かつ V_i > V_j のときに限り、時刻 t > 0 で追い抜きが発生するからです。
    vels = [r[1] for r in runners]
    
    # 速度の値が大きいため（最大 10^9）、座標圧縮を行います。
    # 各速度を、全速度の中での順位（1 から N）に変換します。
    v_sorted = sorted(vels)
    rank_map = {v: i + 1 for i, v in enumerate(v_sorted)}
    ranks = [rank_map[v] for v in vels]
    
    # 転倒数を計算するために Binary Indexed Tree (Fenwick Tree) を使用します。
    # bit[i] は、これまでに処理した要素のうち、順位が i であるものの個数を管理します。
    bit = [0] * (N + 1)
    total_overtakes = 0
    
    # 各速度の順位を順番に処理し、それより大きい順位が既にいくつ現れたかをカウントします。
    for i, r in enumerate(ranks):
        # BITのクエリ：現在までに処理した要素のうち、順位が r 以下のものの個数 s を求めます。
        s = 0
        idx = r
        while idx > 0:
            s += bit[idx]
            idx -= idx & (-idx)
        
        # 現在までに処理した要素の総数は i 個です。
        # そのうち順位が r 以下のものが s 個なので、r より大きいものは (i - s) 個です。
        # これが、現在処理しているランナーよりも「前にいて遅い」ランナーの数になります。
        total_overtakes += (i - s)
        
        # BITの更新：現在のランナーの順位 r を BIT に追加します。
        idx = r
        while idx <= N:
            bit[idx] += 1
            idx += idx & (-idx)
    
    # 最終的な追い抜きの総回数を出力します。
    sys.stdout.write(str(total_overtakes) + '\n')

if __name__ == '__main__':
    solve()

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