Pythonで石を取り除いて最大スコアを求めるプログラム

3つの整数 a、b、c が与えられているとします。それぞれの値をサイズとする3つの石の山を使って、一人用のソリティアゲームを行います。各ターンでは、プレイヤーは異なる2つの空でない山を選び、それぞれから石を1つずつ取り除いて、スコアに1点を加算します。そして、空でない山が2つ未満になった時点でゲームは終了です。この記事では、取得可能な最大スコアを求める方法を解説します。

例として、入力が a = 4、b = 4、c = 6 の場合を考えてみましょう。このとき出力は 7 になります。初期状態は (4, 4, 6) であり、次の手順でゲームを進められるためです。

• 1番目と2番目の山から選ぶ → 現在の状態は (3, 3, 6)

• 1番目と3番目の山から選ぶ → 現在の状態は (2, 3, 5)

• 1番目と3番目の山から選ぶ → 現在の状態は (1, 3, 4)

• 1番目と3番目の山から選ぶ → 現在の状態は (0, 3, 3)

• 2番目と3番目の山から選ぶ → 現在の状態は (0, 2, 2)

• 2番目と3番目の山から選ぶ → 現在の状態は (0, 1, 1)

• 2番目と3番目の山から選ぶ → 現在の状態は (0, 0, 0)

最後には空でない山が2つ未満となるため、ここでゲームは終了します。合計7回の操作でスコア7を達成できました。

解法の考え方

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

• minimum := a、b、c のうちの最小値

• maximum := a、b、c のうちの最大値

• left := a + b + c − maximum − minimum(残るもう1つの山のサイズ)

• もし maximum − left ≤ minimum であるならば:

  • minimum + left − (1 + minimum − (maximum − left)) の商(整数除算)を返す

• そうでなければ:

  • minimum + min(maximum − minimum, left) を返す

なぜこの式で求まるのか

各ターンで必ず2個の石が減っていくため、スコアの理論的な上限は「石の総数 ÷ 2」です。しかし、1つの山が極端に大きい場合、ペアにできる山が先に尽きてしまい、すべての石を使い切ることができません。そこで、最大の山(maximum)と残り2つの山のバランスを確認し、バランスが取れている場合は総数ベースの式で、偏りがある場合は小さい方の山に合わせてスコアを計算することで、効率よく答えを導けます。

実装例(Python)

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

def solve(a, b, c):
   minimum = min(a,b,c)
   maximum = max(a,b,c)
   left = a+b+c-maximum-minimum
   if maximum-left<=minimum:
      return minimum + left-(1+minimum-(maximum-left))//2
   return minimum + min(maximum-minimum,left)

a = 4
b = 4
c = 6
print(solve(a, b, c))

入力

4, 4, 6

出力

7