概要

\(N\) 人の選手がスタミナ値の小さい順にリタイアしていくとき、各選手がリタイアする直前に「残っている選手の中で左から何番目にいるか」を効率的に求める問題です。Binary Indexed Tree（BIT / Fenwick Tree）を用いて高速に順位を計算します。

考察

問題の整理

選手は最初に左から \(1, 2, \ldots, N\) の順に並んでいます。選手 \(i\) のスタミナ値は \(L_i\) であり、スタミナ値が \(1, 2, \ldots, N\) の順にリタイアしていきます。

あるスタミナ値 \(k\) の選手がリタイアするとき、その選手の元の位置（初期位置）は分かっています。問題は「まだ残っている選手の中で、その選手が左から何番目か」を求めることです。

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

素朴に考えると、リタイアのたびに配列から選手を削除し、残りの選手の中での位置を線形探索で求める方法があります。しかし、この方法では各リタイアにつき最大 \(O(N)\) の操作が必要で、全体で \(O(N^2)\) となり、\(N = 2 \times 10^5\) では TLE になります。

解決の鍵

「ある位置より左に、まだ残っている選手が何人いるか」を高速に求められればよいと気づきます。これは区間の累積和を動的に更新しながら計算する問題であり、Binary Indexed Tree（BIT）が最適です。

具体例で考えてみましょう。\(N = 5\), \(L = [3, 1, 4, 5, 2]\) の場合：

• 初期状態：位置 \(0, 1, 2, 3, 4\) にそれぞれ選手 \(1, 2, 3, 4, 5\)（全員残っている）
• スタミナ \(1\) の選手は選手 \(2\)（位置 \(1\)）。位置 \(0\) ～ \(1\) に残っている人数 \(= 2\) → 左から2番目
• 選手 \(2\) を削除。次にスタミナ \(2\) の選手は選手 \(5\)（位置 \(4\)）。位置 \(0\) ～ \(4\) に残っている人数 \(= 4\) → 左から4番目
• …と続けます。

アルゴリズム

1. 前処理: stamina_to_pos[k] = スタミナ値 \(k\) を持つ選手の初期位置（0-indexed）を求める。
2. BIT の初期化: 長さ \(N\) の BIT を用意し、全位置に \(1\) を設定する（全員が残っている状態）。
3. スタミナ値 \(k = 1, 2, \ldots, N\) の順に処理:
   • スタミナ値 \(k\) の選手の初期位置 pos を取得。
   • BIT で区間 \([0, \text{pos}]\) の累積和を求める。これが「残っている選手の中で左から何番目か」に対応する。
   • その位置の値を \(-1\) して BIT を更新（リタイア処理）。
4. 各 \(k\) について求めた順位を出力する。

BIT の操作

• query(i): 位置 \(0\) から \(i\) までに残っている選手の人数を \(O(\log N)\) で求める。
• update(i, -1): 位置 \(i\) の選手をリタイアさせる（カウントを \(1\) 減らす）。\(O(\log N)\)。

計算量

• 時間計算量: \(O(N \log N)\)（BIT の初期化に \(O(N \log N)\)、各リタイアにつき query と update がそれぞれ \(O(\log N)\) で \(N\) 回）
• 空間計算量: \(O(N)\)（BIT と前処理用の配列）

実装のポイント

• BIT は 1-indexed で管理するのが定石です。コード中では 0-indexed の位置に対して内部で +1 しています。

• stamina_to_pos の構築で「スタミナ値 → 初期位置」の逆引きテーブルを作ることで、スタミナ値の小さい順に処理する際に \(O(1)\) で対象選手の位置を特定できます。

• Python では入出力がボトルネックになりやすいため、sys.stdin.buffer.read() でまとめて読み込み、出力も '\n'.join() でまとめて書き出しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    L = [int(input_data[i + 1]) for i in range(N)]
    
    # stamina_to_pos[k] = position (0-indexed) of the player with stamina k
    stamina_to_pos = [0] * (N + 1)
    for i in range(N):
        stamina_to_pos[L[i]] = i  # 0-indexed position
    
    # BIT (Fenwick Tree) to count remaining players
    # bit[i] represents sum over a range, initialized with 1 for each position
    bit = [0] * (N + 1)
    
    def update(i, delta):
        # 1-indexed
        i += 1
        while i <= N:
            bit[i] += delta
            i += i & (-i)
    
    def query(i):
        # sum from index 0 to i (0-indexed), so 1-indexed 1 to i+1
        s = 0
        i += 1
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s
    
    # Initialize: all positions are occupied
    for i in range(N):
        update(i, 1)
    
    out = []
    for k in range(1, N + 1):
        pos = stamina_to_pos[k]  # 0-indexed original position
        # How many players are still present at positions 0..pos (including this player)
        rank = query(pos)
        out.append(str(rank))
        # Remove this player
        update(pos, -1)
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

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