Pythonで解くコイン山ゲーム：プレイヤー1が獲得できるコインの最大数を求めるアルゴリズム

問題概要

コインの山が 3×n 個あり、それぞれ異なる枚数のコインが入っています。ここで、3人のプレイヤーが次のルールでゲームを行います。

• 各ステップで、プレイヤー1は任意の3つの山を選びます。
• 選ばれた3つの山の中から、プレイヤー2は最もコイン数の多い山を取ります。
• 続いて、プレイヤー1は2番目にコイン数の多い山を取ります。
• 最後に残った山はプレイヤー3のものになります。
• この手順を、すべての山がなくなるまで繰り返します。

各山のコイン数を格納した整数配列 piles（piles[i] は i 番目の山のコイン数）が与えられたとき、プレイヤー1が獲得できるコインの最大数を求めるのが本問題です。

具体例

piles = [2,4,1,2,7,8] の場合、答えは 9 になります。まず三つ組 (2,7,8) を選ぶと、プレイヤー2が 8 を取り、プレイヤー1が 7 を取り、残りの 2 はプレイヤー3へ渡ります。次に三つ組 (1,2,4) を選ぶと、プレイヤー2が 4 を取り、プレイヤー1が 2 を取り、残りの 1 はプレイヤー3へ。このときプレイヤー1の手元には 7+2 = 9 枚のコインがあり、これが達成可能な最大値です。

解法アプローチ：貪欲法

この問題は貪欲法（グリーディ法）で効率的に解けます。配列を昇順にソートしておけば、各ラウンドで「最小の山をプレイヤー3に譲り、最大の山をプレイヤー2に渡し、自分は2番目に大きい山を取る」のが最適戦略になります。これにより、毎回確実に残りの中で2番目に大きなコイン数を確保でき、合計が最大化されます。

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

• リスト piles をソートします。
• 変数 ans := 0 を用意します。
• piles が空になるまで、次の操作を繰り返します。
  • ans := ans + 後ろから2番目の要素
  • 後ろから2番目の要素を削除
  • 末尾の要素を削除
  • 先頭の要素を削除
• 最終的な ans を返します。

実装例（Python）

def solve(piles):
    piles.sort()
    ans = 0
    while len(piles) != 0:
        ans = ans + piles[-2]
        del piles[-2]
        del piles[-1]
        del piles[0]
    return ans

piles = [2,4,1,2,7,8]
print(solve(piles))

入力

[2,4,1,2,7,8]

出力

9

計算量

ソートに O(n log n)、各ラウンドの処理は全体で O(n) となるため、時間計算量は O(n log n) です。追加のメモリ使用量は O(1)（入力リスト自体を書き換える場合）で、非常に効率的な解法といえます。