概要

\(N\) 人の生徒がグループ対抗戦を行うクイズ大会において、各ラウンドで各グループの最強者（実力値最大、同点なら出席番号最小）が勝ち残り、最終的に1人になるまで戦い続ける。最後に残る生徒の出席番号を求めよ。

考察

この問題では、生徒たちを \(K\) 人ずつのグループに分け、各グループ内の最強者が次のラウンドへ進むという処理を繰り返す必要があります。

重要なポイントは以下の通りです：

• 生徒の持ち方：単に実力値だけでなく、出席番号も一緒に持たせる必要があります。これは、実力値が同じ場合に出席番号が小さい方を選びたいからです。
• 効率的なシミュレーション：愚直に毎回リストを作ると、特に \(N\) が大きいときに時間がかかりすぎてしまう可能性があります。しかし、Pythonの list や deque を上手く使うことで、十分高速にシミュレーションできます。
• グループ分けの方法：出席番号順に並んでいるので、先頭から \(K\) 個ずつ取っていくだけでOKです。すでに順序が保証されているためソート不要です。

アルゴリズム

1. 生徒を (実力値, 出席番号) の形でリストに保存します。
2. 生徒が1人になるまで以下を繰り返します：
   • 現在の生徒リストを \(K\) 人ずつグループに分けます。
   • 各グループについて、実力値が最大かつ出席番号が最小の生徒を選び出し、次のラウンドのリストに追加します。
3. 最終的に残った1人の出席番号を出力します。

具体的には、各ラウンドで以下のように処理を行います： - students[i:i+K] でグループを取り出し、 - その中で min(group, key=lambda x: (-x[0], x[1])) を使って条件を満たす最強者を選択。

計算量

• 時間計算量: \(O(N)\)
  各ラウンドで全員を一度だけ確認し、ラウンド数は高々 \(\log_K N\) 回なので、全体では線形時間に近いオーダーになります。
• 空間計算量: \(O(N)\)
  生徒情報を保持するリストが必要です。

実装のポイント

• 生徒を (実力値, 出席番号) のタプルで管理することで、勝者の選択が簡単になります。
• min() にキーを指定して、「実力値の降順 → 出席番号の昇順」の優先順位で比較させています。
• 毎ラウンドで新しいリストを作らず、上書きしていけばメモリ効率も良くなるため、next_round を使い回す工夫が重要です。

ソースコード

from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # 生徒を (実力値, 出席番号) で管理 (出席番号は1-indexed)
    students = [(A[i], i+1) for i in range(N)]
    
    while len(students) > 1:
        next_round = []
        # K人ずつグループに分ける
        for i in range(0, len(students), K):
            group = students[i:i+K]
            # 実力値の最大値を持つ生徒を選ぶ
            # 実力値が同じなら出席番号が小さい人を選ぶ
            winner = min(group, key=lambda x: (-x[0], x[1]))
            next_round.append(winner)
        students = next_round
    
    print(students[0][1])

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。