概要

シングルエリミネーション方式のトーナメントをシミュレーションし、各選手が何ラウンド目で敗退するかを求める問題です。

考察

問題の構造を理解する

トーナメントの対戦表は完全二分木の構造をしています。例えば \(N = 8\) の場合を考えましょう。

ラウンド1: (選手1 vs 選手2), (選手3 vs 選手4), (選手5 vs 選手6), (選手7 vs 選手8)
ラウンド2: (試合1の勝者 vs 試合2の勝者), (試合3の勝者 vs 試合4の勝者)
ラウンド3: (試合1の勝者 vs 試合2の勝者) → 優勝者決定

各ラウンドでは、隣り合う2人（リスト上で連続する2人の勝者）が対戦し、強い方が次のラウンドに進みます。負けた選手はそのラウンド番号が敗退ラウンドになります。

素朴なシミュレーションで十分か？

各ラウンドで選手数は半分になるため、全ラウンドの試合数の合計は：

\[\frac{N}{2} + \frac{N}{4} + \cdots + 1 = N - 1\]

つまり、全体で \(N - 1\) 試合しかありません。\(N \leq 2^{19} = 524288\) なので、素朴なシミュレーションでも十分高速に動作します。

アルゴリズム

1. 初期化: 現在残っている選手のリスト current_players を \([0, 1, 2, \ldots, N-1]\)（0-indexed）で初期化する。
2. 各ラウンド \(r = 1, 2, \ldots, \log_2 N\) について:
   • リストの先頭から2人ずつペアにする（第 \(i\) ペア: current_players[2i] と current_players[2i+1]）。
   • 各ペアで強さ \(S\) を比較し、弱い方の敗退ラウンドを \(r\) と記録する。
   • 勝った方だけを次ラウンドのリスト next_players に追加する。
3. 最後に残った1人が優勝者であり、その選手の敗退ラウンドは \(0\) とする（初期値のまま）。

具体例（\(N = 4\), \(S = [3, 1, 4, 2]\)）

• ラウンド1: 選手1(\(S=3\)) vs 選手2(\(S=1\)) → 選手1勝利、選手2はラウンド1で敗退。選手3(\(S=4\)) vs 選手4(\(S=2\)) → 選手3勝利、選手4はラウンド1で敗退。
• ラウンド2: 選手1(\(S=3\)) vs 選手3(\(S=4\)) → 選手3勝利、選手1はラウンド2で敗退。
• 結果: 2 1 0 1（選手3が優勝）

計算量

• 時間計算量: \(O(N)\) — 全ラウンドの試合数の合計が \(N - 1\) であるため。
• 空間計算量: \(O(N)\) — 選手リストや結果配列の保持に必要。

実装のポイント

• N.bit_length() - 1 で \(\log_2 N\) を整数として簡潔に求められます。例えば \(N = 8\) なら bit_length() は \(4\) なので、\(R = 3\) となります。

• 選手番号は1-indexedですが、配列は0-indexedで管理し、出力時に対応させています。

• sys.stdin.read() を使って入力を一括読み込みすることで、大きな入力でもI/Oがボトルネックになりません。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    S = [int(x) for x in input_data[1:N+1]]
    
    # result[i] = round in which player i+1 (0-indexed) loses, 0 for champion
    result = [0] * N
    
    # Simulate the tournament
    # current_players[i] = index (0-based) of the player currently in position i
    current_players = list(range(N))
    
    R = N.bit_length() - 1  # log2(N)
    
    for r in range(1, R + 1):
        num_matches = len(current_players) // 2
        next_players = []
        for i in range(num_matches):
            p1 = current_players[2 * i]
            p2 = current_players[2 * i + 1]
            if S[p1] > S[p2]:
                next_players.append(p1)
                result[p2] = r
            else:
                next_players.append(p2)
                result[p1] = r
        current_players = next_players
    
    print(' '.join(map(str, result)))

main()

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