Pythonで石取りゲームの勝者を求めるプログラムの書き方

問題の概要

Amal（アマル）とBimal（ビマル）がゲームをしていて、Amalが先手であるとします。このゲームは以下のようなルールです。

山の中にn個の石があります。各プレイヤーは順番に山から1個の石を取り、その石の位置に応じたポイントを受け取ります。ただし、AmalとBimalは同じ石を異なる価値で評価する場合があります。

同じ長さを持つ2つの配列 A_Values と B_Values が与えられます。A_Values[i] と B_Values[i] は、それぞれi番目の石に対するAmalとBimalの評価値を表します。すべての石が取り終わった時点で、合計スコアが高い方が勝者となります。スコアが同点の場合は引き分けです。両プレイヤーは最適な戦略でプレイし、互いの評価値も把握しているものとします。

結果として、Amalが勝てば1、Bimalが勝てば -1、引き分けなら0を返します。

入力例

A_Values = [2,4]、B_Values = [3,5] の場合、出力は1になります。これは、Amalが先に4ポイントの2番目の石を選ぶためです。するとBimalは残された3ポイントの1番目の石しか取れず、Amalのスコアの方が高くなるのでAmalの勝利となります。

解法のアプローチ

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

• n を A_Values のサイズとする
• combinedValues という新しいリストを作成する
• i を0からn-1まで繰り返す
  • tmpV := A_Values[i] + B_Values[i]
  • ペア (tmpV, i) を combinedValues の末尾に追加する
• combinedValues を降順にソートする
• score_a := 0、score_b := 0 と初期化する
• i を0からn-1まで繰り返す
  • curV := combinedValues[i]
  • i が偶数（先手の番）の場合
    • score_a := score_a + A_Values[curV[1]]
  • それ以外（後手の番）の場合
    • score_b := score_b + B_Values[curV[1]]
• score_a > score_b なら 1 を返す
• score_a == score_b なら 0 を返す
• それ以外は -1 を返す

なぜこの貪欲法が有効か

各石について「自分の評価値＋相手の評価値」の合計を計算し、その合計値が大きい順に取っていくのが最適戦略です。ある石を取ることは、その石から得られる得点だけでなく、相手がその石から得られたはずの得点を奪うことにもなるため、両者の評価値の合計が大きい石ほど「取る価値」が高いと言えます。したがって、合計値の降順に交互に選択すれば、両者が最適にプレイした場合の結果を正しくシミュレートできます。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(A_Values, B_Values):
   n = len(A_Values)
   combinedValues = []
   for i in range(n):
      tmpV = A_Values[i] + B_Values[i]
      combinedValues.append([tmpV, i])

   combinedValues.sort(reverse=True)

   score_a, score_b = 0, 0
   for i in range(n):
      curV = combinedValues[i]
      if (i % 2 == 0):
         score_a += A_Values[curV[1]]
      else:
         score_b += B_Values[curV[1]]

   if (score_a > score_b):
      return 1
   elif (score_a == score_b):
      return 0
   else:
      return -1

A_Values = [2,4]
B_Values = [3,5]
print(solve(A_Values, B_Values))

入力

[2,4], [3,5]

出力

1