概要

トーナメントの進行をそのままシミュレーションし、各試合で負けた選手に「何ラウンド目で負けたか」を記録していく問題です。
最後まで勝ち残った1人だけが優勝者なので、その選手の答えは \(0\) になります。

考察

この問題のポイントは、対戦相手の組み合わせが完全に固定されていることです。

• ラウンド1は \((1,2), (3,4), \dots\)
• ラウンド2はラウンド1の勝者同士を左から順に
• 以降も同様

つまり、毎ラウンド「現在の並びで隣同士を戦わせる」を繰り返せば、問題文どおりの進行になります。

また、強さ \(S_i\) は全員異なるので引き分けはなく、毎試合の勝者は一意に決まります。
したがって、各試合で

• 負けた側に ans[選手番号] = 現在ラウンド
• 勝った側を次ラウンド配列へ追加

とするだけでOKです。

素朴解法について

「各選手について、どこで負けるかを個別に調べる」ような方法を取ると、同じ試合を何度も再計算して非効率になります。
この問題はトーナメント全体を1回シミュレーションすれば全員分が同時に求まるので、全体をまとめて処理するのが最適です。

アルゴリズム

1. current に現在ラウンドに残っている選手を、トーナメント順で持つ。要素は (strength, index)。
2. round_no = 1 から開始。
3. current の長さが1になるまで繰り返す：
   • 2人ずつ取り出して試合させる。
   • 強い方を nxt に追加（次ラウンド進出）。
   • 弱い方の ans[index] に round_no を記録。
4. ループ終了時、current に残る1人が優勝者なので、その ans[index] = 0。
5. ans を出力。

例として \(N=8\) なら、
ラウンド1で8人→4人、ラウンド2で4人→2人、ラウンド3で2人→1人、のように半分ずつ減っていきます。
この過程で負けた時点のラウンド番号を埋めればよいです。

計算量

• 時間計算量: \(O(N)\)
  （各ラウンドの試合数合計は \(N/2 + N/4 + \cdots + 1 = N-1\)）
• 空間計算量: \(O(N)\)
  （ans と各ラウンドの生存者配列）

実装のポイント

• 選手番号は入力上は \(1\) 始まりですが、実装では 0 始まりインデックスで管理すると配列アクセスが簡単です。

• current には強さだけでなく元の選手番号（index）を持たせることが重要です。
  これがないと「誰の答えを更新するか」が分からなくなります。

• 優勝者はループ中に敗北しないため、最後に明示的に 0 を設定します（初期値0でも、意図を明確にするため設定しておくと安全です）。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    S = list(map(int, input().split()))

    # current players in bracket order: (strength, index)
    current = [(S[i], i) for i in range(N)]
    ans = [0] * N
    round_no = 1

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

    # champion
    ans[current[0][1]] = 0

    print(*ans)

if __name__ == "__main__":
    main()

---

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