概要

選手がスタミナ値の小さい順にリタイアしていくとき、それぞれの選手がリタイアする直前における順位（左からの位置）を求めよ。

考察

この問題では、選手が初期位置から順番に列に並んでいて、スタミナ値の小さい順にリタイアしていきます。リタイアすると列から抜け、残った選手は詰まって左寄せされます。

素朴な方法として、リタイアするたびに実際にリストから削除・詰め合わせを行うと、計算量が \(O(N^2)\) になってしまい、制約 \(N \leq 2 \times 10^5\) では間に合いません。

重要な観察は、「選手の初期位置は固定であり、リタイアの順番だけがスタミナ値によって決まる」という点です。つまり、ある選手の順位は、「自分より左にいる、すでにリタイアした選手の人数」を引いたものになります。

これにより、実際にリストを操作しなくても、リタイアした位置を記録しておけば、二分探索を使って高速に答えを求めることができます。

アルゴリズム

1. 各選手の初期位置を記録します。これは入力のインデックスに対応しており、選手の番号とスタミナ値の関係を逆引きできるようにします。
2. スタミナ値 \(k = 1, 2, \ldots, N\) の順に処理します。
3. 各 \(k\) に対して、スタミナ値 \(k\) を持つ選手の初期位置を取得します。
4. それまでにリタイアした選手の位置を管理するリスト removed_positions（ソート済み）を使い、現在の選手の初期位置より前に何人がリタイアしたかを二分探索で求めます。
5. その人数を引くことで、現在の選手中での順位（1-based）が得られます。
6. 最後に、その選手の位置を removed_positions に挿入します（ソートされた状態を保ちながら）。

計算量

• 時間計算量: \(O(N \log N)\)
  各選手に対して一度の二分探索と一次の挿入操作が必要であり、どちらも \(O(\log N)\)。
• 空間計算量: \(O(N)\)
  pos, removed_positions, result などで線形のメモリを使用。

実装のポイント

• bisect_left を使って、ソートされたリストに挿入すべき位置を高速に求めます。

• insort を使うことで、ソートされた状態を保ちながら要素を挿入できます。

• 選手の番号とスタミナ値の対応を逆引きできるように pos 配列を事前に構築しておくことが重要です。

  ソースコード

import sys
from bisect import bisect_left, insort

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    L = list(map(int, data[1:N+1]))
    
    # 選手の初期位置（1-indexed）を記録
    pos = [0] * (N + 1)  # pos[i] := 選手 i の初期位置（1-based）
    for i in range(N):
        pos[L[i]] = i + 1
    
    # リタイアした選手の位置を管理するリスト（ソートされた状態を維持）
    removed_positions = []
    result = [0] * N  # 結果を格納する配列（0-indexed）

    # スタミナ値 k = 1 から N まで処理
    for k in range(1, N + 1):
        current_pos = pos[k]  # スタミナ値 k の選手の初期位置
        # removed_positions の中で current_pos 未満の要素の個数を求める
        idx = bisect_left(removed_positions, current_pos)
        # 残っている選手中での位置 = 初期位置 - 自分より左にリタイアした人数
        rank = current_pos - idx
        result[k - 1] = rank
        # リタイアした位置を追加
        insort(removed_positions, current_pos)
    
    # 結果を出力
    print('\n'.join(map(str, result)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。