Pythonでレンガ除去ゲームの最大スコアを求めるプログラム

アマルとビマルがゲームをしているとします。配列 nums は、上に番号が書かれた n 個のレンガを表しています。このゲームでは、プレイヤーは交互に山の上から1個、2個、または3個のレンガを取り除くことができ、取り除いたレンガに書かれた数字がそのプレイヤーのスコアに加算されます。常にアマルが先手であるとき、アマルが確保できる最大のスコアを求める必要があります。

例えば、入力が nums = [1,2,3,4,5] の場合、出力は 6 になります。アマルは最初に {1}、{1,2}、{1,2,3} のいずれかを取ることができます。もし最初に2個か3個をまとめて取ると、ビマルが残りをすべて取って最大のスコアを得てしまいます。しかし、アマルが最初に 1 だけを取れば、ビマルは最大でも {2,3,4} = 9 しか取れず、残った 5 をアマルが取ることができます。したがって、アマルの合計スコアは 1 + 5 = 6 となります。

解法のアプローチ

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

• INF := 9999
• n := nums のサイズ
• リスト nums を反転する
• temp := サイズ n の配列を作成し、0 で初期化する
• total := サイズ n の配列を作成し、0 で初期化する
• nums の各インデックス i と値 val に対して、次を実行する
  • total[i] := total[i-1] + val
• temp[0] := nums[0]
• temp[1] := temp[0] + nums[1]
• temp[2] := temp[1] + nums[2]
• i を 3 から n - 1 まで繰り返す
  • a := nums[i]
  • b := nums[i] + nums[i-1]
  • c := nums[i] + nums[i-1] + nums[i-2]
  • temp[i] := a, b, c の最大値
• temp[n-1] を返す

この解法では、まずレンガの並びを反転させることで、配列の末尾が「山の一番上」に対応するようにしています。これにより、先手が選べる選択肢（末尾側から1〜3個の連続したレンガ）を動的計画法で評価しやすくなります。また、配列 total には累積和を格納しておき、任意の区間の合計を効率よく参照できるようにしています。最終的な答えは temp[n-1]、つまり山全体を見たときの先手（アマル）の最大スコアとなります。

実装例

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

INF = 99999
def solve(nums):
   n = len(nums)
   nums.reverse()
   temp = [0]*n
   total = [0]*n
   for i, val in enumerate(nums):
      total[i] = total[i-1] + val
   temp[0] = nums[0]
   temp[1] = temp[0]+nums[1]
   temp[2] = temp[1]+nums[2]
   for i in range(3, n):
      a = nums[i]
      b = nums[i] + nums[i-1]
      c = nums[i] + nums[i-1] + nums[i-2]
      temp[i] = max(a, b, c)
   return temp[n-1]

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

入力

[1,2,3,4,5]

出力

6