【Python】配列ゲームの勝者を見つけるプログラムの実装方法

問題の概要

一意な要素のみを含む配列「arr」と、整数値「k」が与えられているとします。ここで、次のようなゲームを考えてみましょう。

各ターンでは、配列の先頭2つの要素 arr[0] と arr[1] を比較します。大きい方の値が勝者となって位置0に残り、負けた小さい方の値は配列の末尾へ移動します。このゲームは、いずれかの値が k回連続 で勝利した時点で終了し、その時点での勝者が答えとなります。私たちの課題は、この配列から勝者を見つけることです。

具体例

例えば、入力が arr = [1,5,6,3,4,2]、k = 3 の場合、出力は 6 になります。その過程は以下の通りです。

• 第1ラウンド: arr = [1,5,6,3,4,2] → 勝者は 5(5の連続勝利数: 1)
• 第2ラウンド: arr = [5,6,3,4,2,1] → 勝者は 6(6の連続勝利数: 1)
• 第3ラウンド: arr = [6,3,4,2,1,5] → 勝者は 6(6の連続勝利数: 2)
• 第4ラウンド: arr = [6,4,2,1,5,3] → 勝者は 6(6の連続勝利数: 3)

6が3回(k = 3)連続で勝利したため、勝者は 6 となります。

解法のアプローチ

この問題は、実際に配列を操作・並べ替えなくても解けます。ポイントは、配列の最大値が先頭に到達すると、それ以降どの要素もその値に勝てなくなるという性質です。したがって、配列を一度だけ走査すれば答えが求まります。

具体的な手順は以下の通りです。

1. l := 配列arrのサイズ
2. prev := arr[0](現在の勝者候補)
3. count := 0(連続勝利数)
4. i を 1 から l - 1 まで繰り返す:
   • prev > arr[i] の場合:count := count + 1
   • それ以外の場合:prev := arr[i]、count := 1
5. count が k と等しくなったら、prev を返す
6. ループ完了時に条件を満たしていなくても、prev(= 配列の最大値)を返す

Python実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(arr, k):
    l = len(arr)
    prev = arr[0]
    count = 0
    for i in range(1, l):
        if prev > arr[i]:
            count += 1
        else:
            prev = arr[i]
            count = 1
        if count == k:
            return prev
    return prev

arr = [1,5,6,3,4,2]
k = 3
print(solve(arr, k))

入力

[1,5,6,3,4,2], 3

出力

6

計算量について

このアルゴリズムの時間計算量は O(n)(nは配列の長さ)、空間計算量は O(1) です。配列の並べ替えや挿入を実際に行わないため、非常に効率的に動作します。また、ループ内で最大値が現れた時点以降は、その値が最終的な勝者となることも保証されています。