概要

残っている生徒を出席番号順に \(K\) 人ずつのグループに分け、各グループの「実力最大（同点なら番号最小）」だけを残す操作を、1 人になるまで繰り返したときの優勝者（出席番号）を求めます。

考察

各ラウンドでやることは本質的に「現在残っている列を、左から \(K\) 個ずつ区切って、その区間の最大要素（同点は左＝番号が小さい方）を1つ選ぶ」だけです。

ここで重要な観察は次の通りです。

• 各ラウンドは、残っている人数を \(M\) とすると \(O(M)\) で処理できる
  （各生徒は自分の属するグループ内で一度だけ比較される）
• ラウンドを重ねると人数はおおよそ \(M \to \lceil M/K \rceil\) と減るため、全体の処理量は
  \(N + \left\lceil \frac{N}{K}\right\rceil + \left\lceil \frac{N}{K^2}\right\rceil + \cdots\) という等比級数になり、合計で \(O(N)\) 程度に収まります（特に最悪の \(K=2\) でも合計は \(<2N\)）。

逆に、素朴に「グループ分けを毎回作り直す」「勝ち残り判定を重いデータ構造で管理する」などをしても正しくは解けますが、Pythonでは定数倍が大きくなりがちです。本解法はそのままシミュレーションするが、各ラウンドを線形に処理することで高速にします。

また、同点処理は「実力が同じなら出席番号が小さい方」なので、0-index の内部表現では - 実力が大きい方が勝ち - 実力が同じならインデックス（出席番号）が小さい方が勝ち
を比較条件に入れればOKです。

アルゴリズム

1. 残っている生徒のリスト rem を、最初は [0, 1, 2, ..., N-1]（0-index）で持つ。
2. rem の長さが 1 になるまで以下を繰り返す。
   • rem を左から \(K\) 個ずつ見ていき、各ブロック（最後は \(K\) 未満でも可）について
     • そのブロック内で「\((A_i, -i)\) が最大」になる \(i\) を選ぶ
       （実力最大、同点なら \(i\) が小さい＝出席番号が小さい）
     • 選ばれた \(i\) を次ラウンド用リスト new に追加する
   • rem = new として次ラウンドへ
3. 最後に残った 1 人 rem[0] を 1-index に戻して出力する。

例えば \(K=3\)、残りが [2,5,7, 1,4]（出席番号順）なら

• グループ1: [2,5,7] の勝者を選ぶ
  
• グループ2: [1,4] の勝者を選ぶ
  

という処理を毎ラウンド行います。

計算量

• 時間計算量: \(O\!\left(N + \frac{N}{K} + \frac{N}{K^2} + \cdots\right) = O(N)\)
• 空間計算量: \(O(N)\)（残りの生徒番号リストを保持）

実装のポイント

• 同点処理: a2 > bestA or (a2 == bestA and idx2 < best) のように、実力が同じなら番号が小さい方を採用します。

• 高速入出力: \(N \le 5\times 10^5\) なので、sys.stdin.buffer.read() を使った一括読み取り＋手動パースで高速化しています。

• 0-index / 1-index: 内部では 0-index（0..N-1）で扱い、出力時に +1 しています。

  ソースコード

import sys

data = sys.stdin.buffer.read()
n_data = len(data)
i = 0

# Read N
while i < n_data and data[i] <= 32:
    i += 1
N = 0
while i < n_data and data[i] > 32:
    N = N * 10 + (data[i] - 48)
    i += 1

# Read K
while i < n_data and data[i] <= 32:
    i += 1
K = 0
while i < n_data and data[i] > 32:
    K = K * 10 + (data[i] - 48)
    i += 1

A = [0] * N
for t in range(N):
    while i < n_data and data[i] <= 32:
        i += 1
    num = 0
    while i < n_data and data[i] > 32:
        num = num * 10 + (data[i] - 48)
        i += 1
    A[t] = num

rem = list(range(N))
K_local = K
A_local = A

while len(rem) > 1:
    m = len(rem)
    new = []
    new_append = new.append
    rem_local = rem
    i = 0
    while i < m:
        best = rem_local[i]
        bestA = A_local[best]
        end = i + K_local
        if end > m:
            end = m
        j = i + 1
        while j < end:
            idx2 = rem_local[j]
            a2 = A_local[idx2]
            if a2 > bestA or (a2 == bestA and idx2 < best):
                best = idx2
                bestA = a2
            j += 1
        new_append(best)
        i = end
    rem = new

sys.stdout.write(str(rem[0] + 1) + "\n")

---

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