概要

選手がスタミナ値の小さい順にリタイアしていく過程で、各選手がリタイアする直前の左からの位置を求める問題です。

考察

素朴なアプローチとして、実際に各リタイア時に配列から要素を削除し、位置を再計算する方法が考えられます。しかし、配列からの要素削除と詰め直しには \(O(N)\) 時間かかるため、合計で \(O(N^2)\) 時間となり、\(N\) が最大 \(2 \times 10^5\) の場合には時間制限に間に合いません。

効率的な解法として、以下の観察が重要です： - リタイア順はスタミナ値の昇順で固定されている - リタイア前の位置を知るには、それまでにリタイアした選手のうち、現在の選手より左にいた人数を引くことで求められる - データ構造を使って、効率的に要素の削除と順序のクエリを処理できる

アルゴリズム

SortedList（平衡二分探索木の一種）を使用します。最初にすべての選手の初期位置（1-indexed）をリストに保持します。

1. スタミナ値 \(k\) の選手の初期位置を配列 pos_map に記録
2. SortedList に全ての初期位置（1からN）を追加
3. スタミナ値の小さい順（k=1からNまで）に処理：
   • 現在の選手の初期位置を取得
   • SortedList でその位置以下の要素数を二分探索で数える（これが現在の左からの位置）
   • その選手の位置をSortedListから削除

これにより、各ステップで削除とクエリを \(O(\log N)\) 時間で処理できます。

計算量

• 時間計算量: \(O(N \log N)\)
  • SortedListの各操作（挿入、削除、二分探索）が \(O(\log N)\) 時間
  • これをN回繰り返す
• 空間計算量: \(O(N)\)
  • SortedListと補助配列のためのメモリ

実装のポイント

• pos_map でスタミナ値から初期位置へのマッピングを作成

• SortedListの bisect_left で現在の位置以下の要素数を数える

• 要素の削除は remove メソッドで行う

• 出力はスタミナ値1からNの順に対応するため、配列 ans に記録してから順に出力

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    L = list(map(int, data[1:1+n]))
    
    pos_map = [0] * (n + 1)
    for idx, stamina in enumerate(L):
        pos_map[stamina] = idx + 1
        
    ans = [0] * (n + 1)
    from sortedcontainers import SortedList
    sl = SortedList(range(1, n + 1))
    
    for k in range(1, n + 1):
        pos = pos_map[k]
        idx_in_sl = sl.bisect_left(pos)
        ans[k] = idx_in_sl + 1
        sl.remove(pos)
        
    for k in range(1, n + 1):
        print(ans[k])

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。