概要

\(N\) 人の選手が参加するシングルエリミネーション方式のトーナメントにおいて、各選手がどのラウンドで敗退するかをシミュレーションによって求める問題です。

考察

この問題のトーナメント形式は、一般的な「勝ち残り式」の構造をしています。 - \(N\) は \(2\) のべき乗であり、各ラウンドで人数が半分になっていきます。 - 強さが大きい方が必ず勝つため、試合の結果は一意に決まります。 - ラウンドが進むごとに、前のラウンドの勝者同士が順番に対戦します。

例えば \(N=4\) の場合： 1. ラウンド 1：(選手1 vs 選手2)、(選手3 vs 選手4) 2. ラウンド 2：(上の試合の勝者 vs 下の試合の勝者) という流れになります。

\(N\) は最大で \(2^{19} \approx 5.2 \times 10^5\) と比較的大きいですが、各ラウンドで行われる試合数の合計を考えると、 \(\frac{N}{2} + \frac{N}{4} + \dots + 1 = N-1\) となり、全体の試合数は \(N\) に比例する程度です。したがって、愚直に全試合をシミュレーションしても十分に間に合います。

アルゴリズム

以下の手順でシミュレーションを行います。

1. 初期化:

   • 各選手の敗退ラウンドを格納する配列 ans を \(0\) で初期化します。
   • 現在トーナメントに残っている選手の番号（インデックス）を管理するリスト current_indices を用意します。最初は全員 (\(0\) から \(N-1\)) が入っています。

2. シミュレーション:

   • 残っている人数が \(1\) 人になるまで、以下の処理を繰り返します（現在のラウンド番号を \(r\) とします）。
   • current_indices から隣り合う \(2\) 人ずつを取り出し、対戦させます。
   • 強さ \(S\) を比較し、値が小さい方の選手（敗者）の ans[敗者] に \(r\) を記録します。
   • 値が大きい方の選手（勝者）を、次のラウンド用のリスト next_indices に追加します。
   • current_indices を next_indices で更新し、ラウンド番号 \(r\) を \(1\) 増やします。

3. 出力:

   • 最終的に ans 配列を出力します。一度も負けなかった選手（優勝者）は初期値の \(0\) のままとなります。

計算量

• 時間計算量: \(O(N)\)
  • トーナメント全体の試合数は \(N-1\) 試合です。各試合の勝敗判定とリストへの追加は \(O(1)\) で行えるため、全体で \(O(N)\) となります。
• 空間計算量: \(O(N)\)
  • 選手の強さ、敗退ラウンド、現在残っている選手のリストを保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• インデックスの管理: 選手の番号は \(1\) から \(N\) ですが、プログラミング言語の配列の添字に合わせて \(0\) から \(N-1\) で管理すると扱いやすくなります。

• 効率的な入出力: \(N\) が大きいため、Python の場合は sys.stdin.read().split() や sys.stdout.write を使うことで、入出力の時間を短縮できます。

  ソースコード

import sys

def solve():
    # 標準入力から全てのデータを取得し、スペース区切りで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N（参加人数）を取得します
    n = int(input_data[0])
    # 各選手の強さ S_1, S_2, ..., S_N をリストとして取得します
    s = list(map(int, input_data[1:]))
    
    # 各選手が敗退したラウンドを記録する配列（0で初期化、0は優勝者を意味する）
    # ans[i] は選手 i+1 の敗退ラウンドを格納します
    ans = [0] * n
    
    # 現在トーナメントに残っている選手のインデックス（0-indexed）をリストで管理します
    current_indices = list(range(n))
    
    round_num = 1
    # トーナメントの残り人数が1人になるまでシミュレーションを繰り返します
    while len(current_indices) > 1:
        next_indices = []
        # 隣り合う2人ずつを対戦させます
        # ラウンド r において、前のラウンドの第 2j-1 試合と第 2j 試合の勝者が対戦するルールに対応します
        for i in range(0, len(current_indices), 2):
            idx1 = current_indices[i]
            idx2 = current_indices[i+1]
            
            # 強さの値が大きい選手が勝ちます
            if s[idx1] > s[idx2]:
                # 選手 idx2 がこのラウンドで敗退
                ans[idx2] = round_num
                # 勝った選手 idx1 は次のラウンドへ進出
                next_indices.append(idx1)
            else:
                # 選手 idx1 がこのラウンドで敗退
                ans[idx1] = round_num
                # 勝った選手 idx2 は次のラウンドへ進出
                next_indices.append(idx2)
        
        # 次のラウンドに進む選手のリストを更新します
        current_indices = next_indices
        round_num += 1
        
    # 結果をスペース区切りで1行に出力します
    sys.stdout.write(" ".join(map(str, ans)) + "\n")

if __name__ == "__main__":
    solve()

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