\(n\) が偶数である方が実装と考察がしやすいため、今後 \(s\) を \(2\) つ並べたものを \(s\) として問題を解くことにします（答えは変わりません）。

各選手が最初の試合を終えた直後に、勝ち残ってる選手のうち \(i\) 番目に小さい整数の参加者について考えます（この解説では、問題文の整数の振り方と同じように、一番小さい整数を \(0\) 番目と呼ぶことにします）。対戦の方法から、これは番号 \(2i\) の参加者と番号 \(2i+1\) の参加者が試合をしたときの勝者であることが分かります。よって、各選手が最初の試合を終えた直後に勝ち残ってる選手の得意な手を順番に並べた文字列を考えると、\(i\) 番目の文字は \(s_{2i}\) と \(s_{2i+1}\) のうち負けない方の手です。 この状態は、参加者の得意な手が、以下で定義される文字列 \(t\) で表され、参加者の人数が \(2^{k-1}\) 人だった場合と同じです。

for i = 0, 2, ... ,n-2
    t[i/2] = s[i] と s[i+1] のうち負けない方の手

よって、この処理を \(k\) 回繰り返した文字列の最初の文字が答えとなります。

C++による実装