概要

この問題は、\(N\)人の生徒をグループ分けして勝ち抜き戦を行い、最終的な優勝者を求める問題です。各グループでは実力値が最も高い生徒（同値の場合は出席番号が小さい生徒）が勝ち残ります。

考察

素朴なアプローチでは、各ラウンドで実際にグループ分けと勝者の選出をシミュレーションします。しかし、各ラウンドでグループの数は約 \(N/K\) 個になり、ラウンド数は \(\log_K N\) 回程度になるため、全体の計算量は \(O(N \log_K N)\) となります。\(N\) の最大値が \(500,000\) であり、\(K\) が大きい場合（例えば \(K\) が \(N\) に近い場合）はラウンド数が少なく効率的ですが、\(K\) が小さい場合（例えば \(K=2\)）はラウンド数が \(\log_2 N \approx 19\) 回程度なので、十分に効率的です。

アルゴリズム

1. すべての生徒を出席番号順（＝入力順）にキューに格納します。各要素は（実力値, 出席番号）のタプルとします。
2. キューに残っている生徒が1人になるまで以下を繰り返します：
   • キューから先頭から \(K\) 人ずつ取り出してグループを形成します（最後のグループは \(K\) 人未満でも可）
   • 各グループ内で最大の実力値を持つ生徒を選びます（同値の場合は出席番号が小さい生徒を選ぶ）
   • 選ばれた勝者を新しいキューに追加します
3. 最後に残った生徒の出席番号を出力します

計算量

• 時間計算量: \(O(N \log_K N)\)
  • 各ラウンドの処理が \(O(N)\)、ラウンド数が \(O(\log_K N)\) のため
• 空間計算量: \(O(N)\)
  • キューを使用するため

実装のポイント

• deque を使用することで、グループ分け時の要素の取り出しと追加を効率的に行えます

• 各生徒を（実力値, 出席番号）のタプルで管理することで、max 関数を用いて簡単に勝者を選べます

• max 関数のキーとして (x[0], -x[1]) を指定することで、実力値が最大で、同値の場合は出席番号が最小の生徒を選べます

• グループ分け時には、キューが空になるか、グループが \(K\) 人になるまで取り出しを行います

  ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    students = deque()
    for i in range(n):
        students.append((A[i], i + 1))
    
    while len(students) > 1:
        new_round = deque()
        group = []
        
        while students:
            group.append(students.popleft())
            if len(group) == k or not students:
                winner = max(group, key=lambda x: (x[0], -x[1]))
                new_round.append(winner)
                group = []
        
        students = new_round
    
    print(students[0][1])

if __name__ == "__main__":
    main()

---

この解説は deepseekv3 によって生成されました。