概要

トーナメントの組み合わせは完全に固定されており、しかも「強い方が必ず勝つ」ので、ラウンドごとにそのまま勝者を残していけばよいです。
各試合の敗者に「何ラウンド目で負けたか」を記録し、最後まで残った 1 人の答えを \(0\) にします。

考察

この問題の重要な点は次の 2 つです。

• 対戦結果は強さを 1 回比較するだけで決まる
• トーナメント表の並び順は最初から最後まで固定されている

重要な観察

ラウンド \(1\) では

• 選手 \(1\) vs 選手 \(2\)
• 選手 \(3\) vs 選手 \(4\)
• …

と戦います。

そして次のラウンドでは、その勝者たちが

• 第 1 試合の勝者 vs 第 2 試合の勝者
• 第 3 試合の勝者 vs 第 4 試合の勝者
• …

という形で戦います。

つまり、そのラウンドに残っている選手をトーナメント順に並べて持っておけば、隣り合う 2 人ずつを戦わせるだけで次のラウンドを作れるということです。

素朴な考え方

各選手について

• どの相手と当たるか
• どのラウンドで自分より強い選手に当たるか

を個別に考えることもできますが、これは人ごとに調べると複雑で、実装も重くなりがちです。

どう解決するか

実際には、トーナメント全体の試合数は全部で \(N-1\) 試合しかありません。
なので、全試合を 1 回ずつシミュレーションすれば十分です。

各ラウンドで

1. 今残っている選手の列 current を見る
2. 2 人ずつ比較する
3. 負けた選手の答えをそのラウンド番号にする
4. 勝った選手だけを nxt に入れる

これを 1 人になるまで繰り返せば答えが求まります。

例

例えば \(N=8\) で、今のラウンドの生存者が

[0, 1, 2, 3, 4, 5, 6, 7]

（内部では 0-indexed）だとします。

ラウンド \(1\) では

• 0 vs 1
• 2 vs 3
• 4 vs 5
• 6 vs 7

を戦わせ、勝者だけを順番に nxt に入れます。
すると nxt は次のラウンドの並びそのものになります。

この「順番を保ったまま勝者を並べる」ことがポイントです。

アルゴリズム

1. current = [0, 1, 2, ..., N-1] を用意する
   
   • ここには「今のラウンドに残っている選手の番号」を順番通りに入れる
2. ans を長さ \(N\) の配列で \(0\) 初期化する
   
   • 優勝者は最後まで更新されないので、そのまま \(0\) になる
3. round_num = 1 とする
4. current の長さが 1 になるまで以下を繰り返す
   • 空の配列 nxt を作る
   • current を 2 つずつ見る
   • 選手 a, b の強さ S[a], S[b] を比較する
   • 強い方を nxt に追加する
   • 負けた方の ans に round_num を記録する
   • ラウンド終了後、current = nxt にする
   • round_num += 1
5. ans を出力する

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

時間計算量が \(O(N)\) である理由

各試合は 1 回しか処理しません。
シングルエリミネーションの試合数は全部で

\(N/2 + N/4 + \cdots + 1 = N-1\)

なので、全体で \(O(N)\) です。

実装のポイント

• current には強さではなく選手の添字を入れる
  こうすると
  • 強さ比較は S[a] > S[b]
  • 答えの記録は ans[a], ans[b]

のように簡単に書けます。 - 勝者を必ず元の順番のまま nxt に入れることが重要です。
順番が崩れると、次ラウンドの対戦相手が変わってしまいます。 - このコードでは ans を最初に全部 \(0\) で初期化しているので、最後まで負けない優勝者は自動的に \(0\) のままになります。 - array('I') を使うことで、大きな入力でもメモリを節約できます。

ソースコード

import sys
from array import array

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    S = array('I', map(int, input().split()))
    ans = array('I', [0]) * N

    current = list(range(N))
    round_num = 1

    while len(current) > 1:
        nxt = []
        append = nxt.append
        for i in range(0, len(current), 2):
            a = current[i]
            b = current[i + 1]
            if S[a] > S[b]:
                ans[b] = round_num
                append(a)
            else:
                ans[a] = round_num
                append(b)
        current = nxt
        round_num += 1

    sys.stdout.write(' '.join(map(str, ans)))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。