概要

選手が特定の順番で列から抜けていくとき、抜ける直前にその選手が列の中で左から何番目にいたかを高速に求める問題です。

考察

問題文の通りに「配列から要素を削除し、残りの要素を左に詰め直す」という操作を素朴にシミュレーション（例えばPythonのリストの pop() などを利用）すると、1回の削除に \(O(N)\) の時間がかかります。これを \(N\) 人分繰り返すと全体の計算量が \(O(N^2)\) となり、制約の \(N \le 2 \times 10^5\) では実行時間制限（TLE）に引っかかってしまいます。

この問題を高速に解くための重要な気づきは、「実際に列を詰め直すのではなく、各選手の初期位置を固定したまま『まだ列に残っているか』を \(1\) と \(0\) で管理する」 という視点の転換です。

例えば、全員が残っている初期状態を \(1\)、リタイアした状態を \(0\) とします。 このとき、ある選手がリタイアする直前に「左から何番目にいるか」は、「列の左端からその選手の初期位置までに、まだ残っている選手（値が \(1\) の位置）がいくつあるか」 を数えることと同じになります。

つまり、以下の2つの操作を高速に行えればよいことになります。 1. 区間和の取得: 左端からある位置までの \(1\) の合計を求める。 2. 一点更新: ある位置の値を \(1\) から \(0\) に変更する（リタイアの処理）。

これらの操作をどちらも \(O(\log N)\) で行えるデータ構造として、Binary Indexed Tree (BIT / フェニック木) や セグメント木 があります。今回は実装が軽量な BIT を使用します。

アルゴリズム

1. 初期位置の記録: スタミナ値 \(k\) の選手が最初に左から何番目にいたかを記録する配列 pos を作成します。入力のスタミナ値 \(L_i\) を読み込みながら、pos[L_i] = i + 1 と記録します（1-indexed）。

2. BITの初期化: 長さ \(N\) の BIT を用意し、最初は全員が残っているため、すべての位置（\(1\) から \(N\)）に \(1\) を加算して初期化します。

3. クエリの処理: スタミナ値 \(k = 1, 2, \ldots, N\) の順番で以下の処理を行います。

   • 選手 \(k\) の初期位置 p = pos[k] を取得します。
   • BIT を使って、位置 \(1\) から \(p\) までの和を求めます。これが「リタイア直前に左から何番目にいたか」の答えになります。
   • 選手 \(k\) がリタイアするため、BIT の位置 \(p\) に \(-1\) を加算し、値を \(0\) に更新します。

4. 出力: 求めた答えを順番に出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 選手の初期位置の記録と BIT の初期化に \(O(N)\) かかります。
  • 各選手について、BIT を用いた区間和の取得と一点更新にそれぞれ \(O(\log N)\) かかります。これを \(N\) 回繰り返すため \(O(N \log N)\) となります。
  • 全体として非常に高速であり、制限時間内に余裕で処理を終えることができます。
• 空間計算量: \(O(N)\)
  • 選手の初期位置を保持する配列 pos と、BIT のデータを保持する配列 bit にそれぞれ \(O(N)\) のメモリを使用します。

実装のポイント

• BITのインデックス: BIT はビット演算（i & -i）を利用する性質上、配列のインデックスを \(1\) 始まり（1-indexed）にして実装すると非常にシンプルになります。

• 高速な入出力: Python では input() を何度も呼ぶと遅延の原因になるため、sys.stdin.read().split() を使って入力を一括で読み込むと実行時間を大幅に短縮できます。出力もリストに文字列としてためておき、最後に \n.join() でまとめて出力すると効率的です。

• BITの線形時間初期化: BITに \(1\) ずつ add していくと初期化に \(O(N \log N)\) かかりますが、正解コードのように親ノードへ自身の値を伝播させる方法をとることで、初期化を \(O(N)\) で行うことができます。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    L = [int(x) for x in data[1:]]
    
    pos = [0] * (N + 1)
    for i in range(N):
        pos[L[i]] = i + 1
        
    bit = [0] * (N + 1)
    for i in range(1, N + 1):
        bit[i] += 1
        nxt = i + (i & -i)
        if nxt <= N:
            bit[nxt] += bit[i]
            
    def add(idx, val):
        while idx <= N:
            bit[idx] += val
            idx += idx & (-idx)
            
    def query(idx):
        s = 0
        while idx > 0:
            s += bit[idx]
            idx -= idx & (-idx)
        return s

    ans = []
    for k in range(1, N + 1):
        p = pos[k]
        ans.append(str(query(p)))
        add(p, -1)
        
    print('\n'.join(ans))

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。