概要

\(N\) 人の生徒を出席番号順に \(K\) 人ずつのグループに分け、各グループで実力値が最大の生徒だけを残す操作を、残り1人になるまで繰り返し、最終的な優勝者を求める問題です。

考察

問題の構造を理解する

この問題はトーナメント形式の勝ち抜き戦です。各ラウンドで生徒を先頭から \(K\) 人ずつグループに分け、各グループの「最強者」だけが生き残ります。

具体例: \(N = 7, K = 3\)、実力値が \(A = [3, 1, 4, 1, 5, 9, 2]\) の場合

• ラウンド1: 生徒を \(K=3\) 人ずつに分ける
  • グループ1: 生徒1(3), 生徒2(1), 生徒3(4) → 生徒3(実力値4)が勝利
  • グループ2: 生徒4(1), 生徒5(5), 生徒6(9) → 生徒6(実力値9)が勝利
  • グループ3: 生徒7(2) → そのまま生徒7が残る
  • 残り: [生徒3, 生徒6, 生徒7]
• ラウンド2: 3人を1グループ
  • グループ1: 生徒3(4), 生徒6(9), 生徒7(2) → 生徒6(実力値9)が優勝

計算量について

各ラウンドでは残っている全生徒を1回ずつ走査するので \(O(n)\)（\(n\) はそのラウンドの人数）です。1ラウンドごとに人数は約 \(1/K\) 倍に減るため、全ラウンドの合計処理量は等比級数 \(N + N/K + N/K^2 + \cdots\) となり、\(O\left(\frac{NK}{K-1}\right) = O(N)\) です。\(K \geq 2\) なので十分高速に動作します。

素朴なシミュレーションで十分

この問題では人数が急速に減少するため、特別なデータ構造やアルゴリズムを使わず、素直にシミュレーションするだけで制限時間に収まります。

アルゴリズム

1. 各生徒を (出席番号, 実力値) のペアとしてリストに格納する。
2. リストの要素数が2以上の間、以下を繰り返す：
   • リストを先頭から \(K\) 個ずつのグループに区切る。
   • 各グループ内で、実力値が最大の生徒を選ぶ。実力値が同じなら出席番号が最小の生徒を選ぶ。
   • 選ばれた生徒だけを新しいリストに入れる。
3. 最後に残った1人の出席番号を出力する。

計算量

• 時間計算量: \(O(N)\)
  • 各ラウンドで全員を走査し、人数は毎ラウンド \(1/K\) 倍に減少するため、総走査回数は \(N \cdot \frac{K}{K-1} = O(N)\)。
• 空間計算量: \(O(N)\)
  • 生徒のリストを保持するため。

実装のポイント

• 勝者の選び方: グループ内で (実力値, -出席番号) が最大の生徒を選べばよいですが、コードでは明示的に条件分岐して「実力値が大きい、または実力値が同じで出席番号が小さい」生徒を選んでいます。

• 最後のグループの処理: end = min(i + K, n) とすることで、最後のグループが \(K\) 人未満でも正しく処理されます。

• 高速入力: sys.stdin.buffer.read() を使って入力を一括読み込みし、Python での入力処理を高速化しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    
    # Store (ability, index) - we want max ability, then min index
    # survivors is a list of (original_index, ability)
    survivors = []
    for i in range(N):
        survivors.append((i + 1, int(input_data[2 + i])))
    
    while len(survivors) > 1:
        new_survivors = []
        n = len(survivors)
        i = 0
        while i < n:
            end = min(i + K, n)
            # Find the winner in this group: max ability, then min index
            best_idx = i
            best_a = survivors[i][1]
            best_id = survivors[i][0]
            for j in range(i + 1, end):
                a = survivors[j][1]
                sid = survivors[j][0]
                if a > best_a or (a == best_a and sid < best_id):
                    best_a = a
                    best_id = sid
                    best_idx = j
            new_survivors.append(survivors[best_idx])
            i = end
        survivors = new_survivors
    
    print(survivors[0][0])

main()

この解説は claude4.6opus-thinking によって生成されました。