バドミントン対戦シミュレーション：K回連続勝利するプレイヤーを効率的に求めるアルゴリズム

1からnまでの数字がシャッフルされた順で並んだ長さnの配列と、整数Kが与えられます。n人のプレイヤーがバドミントンを行うために列に並んでいます。最初の2人が対戦し、負けたプレイヤーは列の末尾に移動します。勝ったプレイヤーは列の先頭に残り、次のプレイヤーと対戦します。この流れを繰り返し、誰かがK回連続で勝利した時点で、そのプレイヤーが勝者となります。

具体例

列が [2, 1, 3, 4, 5]、K = 2 の場合を考えてみましょう。出力は 5 になります。以下に対戦の流れを示します。

• (2, 1) が対戦し、2が勝利 → 1は列の末尾へ。列は [3, 4, 5, 1]
• (2, 3) が対戦し、3が勝利 → 2は列の末尾へ。列は [4, 5, 1, 2]
• (3, 4) が対戦し、4が勝利 → 3は列の末尾へ。列は [5, 1, 2, 3]
• (4, 5) が対戦し、5が勝利 → 4は列の末尾へ。列は [1, 2, 3, 4]
• (5, 1) が対戦し、5が勝利 → 1は列の末尾へ。列は [2, 3, 4, 1]

5が2回連続で勝利したため、答えは 5 となります。

アルゴリズムのポイント

この問題の鍵は、実際のキュー操作を繰り返す必要がない点です。数値が大きいプレイヤーが常に勝つため、配列を先頭から順に走査し、「現在の最強プレイヤー」と「その連勝数」を追跡するだけで答えが求まります。また、Kがn-1以上の場合は、最大値の要素が必ず勝者となるため、即座にnを返すことで計算を省略できます。

winner(arr, n, k)

Begin
    if k >= n-1, then return n
    best_player := 0
    win_count := 0
    for each element e in arr, do
        if e > best_player, then
            best_player := e
            if e is 0th element, then
                win_count := 1
            end if
        else
            increase win_count by 1
        end if
        if win_count >= k, then
            return best player
    done
    return best player
End

C++による実装例

#include <iostream>
using namespace std;
int winner(int arr[], int n, int k) {
    if (k >= n - 1) // Kが配列サイズ以上なら、最大値nが勝者
        return n;
    int best_player = 0, win_count = 0; // 最強プレイヤーと連勝数を初期化
    for (int i = 0; i < n; i++) { // 配列の各要素を順に確認
        if (arr[i] > best_player) { // 現在の最強より強ければ更新
            best_player = arr[i];
            if (i) // 先頭要素でない場合、連勝数を1に設定
            win_count = 1;
        }else // それ以外は連勝数を増やす
        win_count += 1;
        if (win_count >= k) // 連勝数がKに達したら結果確定
            return best_player;
    }
    return best_player; // 連勝数がKに達しない場合、最大要素が勝者
}
main() {
    int arr[] = { 3, 1, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << winner(arr, n, k);
}

出力

3

この実装では、配列を一度だけ走査するため、時間計算量はO(n)となり、非常に効率的に答えを求められます。