概要

\(N\) 人の生徒を \(K\) 人ずつのグループに分け、各グループの勝者（実力値が最大、同点なら出席番号が最小）が次のラウンドに進むというルールで、最後の 1 人（優勝者）が決まるまでシミュレーションを行う問題です。

考察

一見すると、何ラウンドも繰り返すため計算量が多くなるように見えますが、各ラウンドで生き残る人数がどのように変化するかを考えてみましょう。

1 ラウンドごとに、人数はおよそ \(\frac{1}{K}\) 倍になります。\(K \geq 2\) であるため、各ラウンドの参加人数の合計は以下のようになります。

\(\displaystyle N + \frac{N}{K} + \frac{N}{K^2} + \frac{N}{K^3} + \dots\)

これは等比級数の和の公式から、最大でも \(2N\) 程度に収まることがわかります。したがって、愚直に各ラウンドの対戦をシミュレーションしても、全体の計算量は \(N\) の線形時間で済み、制限時間内に十分に間に合います。

勝者の判定条件については、「実力値が最大の人、同じなら出席番号が最小の人」というルールがあります。出席番号の小さい順にグループ内を走査し、「暫定の最大値よりも厳密に大きい実力値が現れた場合のみ更新する」という処理を行えば、自然に出席番号が最小の生徒が選ばれます。

アルゴリズム

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

1. 初期化: 現在の生存者リスト survivors を \([0, 1, \dots, N-1]\) （出席番号から 1 引いたもの）とする。
2. ラウンドの反復: survivors の要素数が 1 より大きい間、以下を繰り返す。
   a. 次のラウンドの生存者リスト next_survivors を空で作成する。
   b. survivors を先頭から \(K\) 人ずつ取り出し、グループを作る。
   c. 各グループの中で、実力値 \(A_i\) が最大となる生徒を探す。実力値が同じ場合は、グループ内でより左側（＝出席番号が小さい）にいる生徒を優先する。
   d. グループの勝者を next_survivors に追加する。
   e. survivors を next_survivors で更新する。
3. 出力: 最後に残った 1 人の出席番号に 1 を足して出力する。

計算量

• 時間計算量: \(O(N)\)
  • 前述の通り、全ラウンドを通した比較回数の合計は \(N\) の定数倍に収まります。
• 空間計算量: \(O(N)\)
  • 実力値を格納する配列 \(A\) と、生存者を管理するリストに \(O(N)\) のメモリを使用します。

実装のポイント

• 効率的な入力: \(N\) が最大 \(5 \times 10^5\) と大きいため、Python では input() を繰り返すのではなく、sys.stdin.read().split() などを用いて一括で読み込むと高速です。
• タイブレークの処理: グループ内の勝者を決める際、if A[curr_idx] > max_strength: と比較演算子を > にすることで、実力値が同じ場合に「先に出現した（＝出席番号が小さい）生徒」を保持し続けることができます。
• メモリ管理: 生存者リストを更新する際、古いリストが不要になったらメモリを解放するように意識すると、メモリ制限が厳しい問題でも安心です。pythonではリストの再代入で古いリストは自動的にガベージコレクションの対象になります。

ソースコード

import sys
import itertools

def solve():
    # 全ての入力を一度に読み込み、空白で分割してリストにする
    # sys.stdin.read().split() は大量の入力を高速に読み込むのに適している
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 生徒の人数 N と、グループの人数 K
    N = int(input_data[0])
    K = int(input_data[1])
    
    # 各生徒の実力値を整数リスト A に変換
    # itertools.islice を使うことで、スライスによる新しいリスト作成を避け、メモリを節約する
    A = list(map(int, itertools.islice(input_data, 2, None)))
    
    # 不要になった文字列リストを削除してメモリを解放
    del input_data
    
    # 現在残っている生徒の出席番号（0-indexed）を管理するリスト
    # 最初は 0, 1, ..., N-1 で、これは出席番号の昇順になっている
    survivors = list(range(N))
    
    # 生徒が1人になるまでラウンドを繰り返す
    while len(survivors) > 1:
        next_survivors = []
        n_surv = len(survivors)
        
        # 現在の生存者を K 人ずつのグループに分ける
        for i in range(0, n_surv, K):
            # 各グループ内での勝者を決定する
            # グループの範囲は survivors[i] から survivors[limit-1]
            limit = i + K
            if limit > n_surv:
                limit = n_surv
            
            # グループの最初の生徒を暫定的な勝者とする
            best_idx = survivors[i]
            max_strength = A[best_idx]
            
            # グループ内の他の生徒と比較
            for j in range(i + 1, limit):
                curr_idx = survivors[j]
                # 実力値が高い生徒がいれば更新
                # 実力値が同じ場合は、出席番号が小さい（先に出現した）生徒を優先するため、
                # 厳密に大きい場合のみ更新する
                if A[curr_idx] > max_strength:
                    max_strength = A[curr_idx]
                    best_idx = curr_idx
            
            # グループの勝者を次のラウンドの生存者リストに追加
            next_survivors.append(best_idx)
        
        # 生存者リストを更新
        survivors = next_survivors
        
    # 最終的な優勝者の出席番号（1-indexed）を出力
    sys.stdout.write(str(survivors[0] + 1) + '\n')

if __name__ == '__main__':
    solve()

---

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