Pythonで配列除去ゲームの勝者を求めるプログラム

AmalとBimalが、いくつかの数値を含む1つの配列Aを使ってゲームを行うことを考えます。ゲームのルールは以下の通りです。

• 必ずBimalが先手です。
• 各ターンで、プレイヤーは配列内の最大要素を削除し、その要素より右側にあるすべての要素も同時に削除します。
• 2人のプレイヤーは交互に手番を行います。
• 残りの要素をすべて取り除いたプレイヤーが勝者となります。

例えば、入力が nums = [5,2,6,3,4] の場合、出力は「Amal」になります。まずBimalが最大要素の6とその右側の要素[3,4]を削除して配列は[5,2]となり、次にAmalが残りの要素をすべて削除するため、勝者はAmalです。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• maximum := -1、count := 0 として初期化します。
• 配列numsの各要素aに対して、以下を繰り返します。
  • a > maximum の場合、count を1増やし、maximum := a と更新します。
• 最後に、count を2で割った余りが0(偶数)なら「Amal」を返し、そうでなければ「Bimal」を返します。

このアルゴリズムのポイントは、「左から順に見たときにそれまでの最大値を更新する要素」(接頭辞最大値)の個数を数える点にあります。この個数がゲーム全体の手数と一致するため、その偶奇を調べるだけで勝者を判定できます。

実装例

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

def solve(nums):
   maximum = -1
   count = 0
   for a in nums:
      if a > maximum:
         count += 1
         maximum = a
   if count % 2 == 0:
      return "Amal"
   return "Bimal"

nums = [5,2,6,3,4]
print(solve(nums))

入力

[5,2,6,3,4]

出力

Amal