Pythonで石のゲームの勝者を見つけるためのプログラム

AmalとBimalがゲームをプレイしていて、Amalの番が最初であるとします。ゲームは以下のようなものです-

石が山積みになっています。各プレイヤーは山から石を取り、その石の位置に基づいてポイントを受け取ることができます。アマルとビマルは石を異なる方法で評価するかもしれません。

同じ長さの2つの配列、A_ValuesとB_Valuesがあります。各A_Values[i]とB_Values[i]は、それぞれAmalとBimalがi番目の石をどのように評価するかを表します。ここでスコアが最大の場合、すべての石が取り出された後、彼が勝者になります。同点の場合、ゲームは引き分けになります。両方のプレイヤーが最適にプレイします。どちらも相手の価値観を知っています。したがって、Amalが勝った場合は、1を返します。Bimalが勝った場合は、-1を返します。そして、引き分けの試合の場合は、0を返します。

したがって、入力がA_Values =[2,4] B_Values =[3,5]の場合、Amalはポイント4で2番目の石を選択するため、出力は1になります。したがって、Bimalはポイントで最初の石を取得する機会が1回だけです。 3ですが、アマルのスコアが高いため、勝ちます。

これを解決するには、次の手順に従います-

• n：=A_Valuesのサイズ
• combinedValues：=新しいリスト
• 0からnの範囲のiについては、
  • tmpV：=A_Values [i] + B_Values [i]
  • ペア（temV、i）を最後にcombinedValuesに挿入します
• リストcombinedValuesを逆の順序で並べ替えます
• score_a：=0、score_b：=0
• 0からn-1の範囲のiの場合、do
  • curV：=CombinedValues [i]
  • i mod 2が0と同じ場合、
    • 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

例

理解を深めるために、次の実装を見てみましょう-

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