Pythonで3つの数値をすべて0にする最小ステップ数を求める方法

はじめに

3つの整数が与えられたとき、「1回の操作で任意の2つの数からそれぞれ1を引く」というルールに従って、すべての数を0にするまでに必要な最適なステップの総数を求める問題です。

例

入力:

a = 4
b = 4
c = 6

出力:

7

解説:

(4, 4, 6) の状態から、以下の手順で操作を進めます。

• 1番目と2番目の数から1を引く → (3, 3, 6)
• 1番目と3番目の数から1を引く → (2, 3, 5)
• 1番目と3番目の数から1を引く → (1, 3, 4)
• 1番目と3番目の数から1を引く → (0, 3, 3)
• 2番目と3番目の数から1を引く → (0, 2, 2)
• 2番目と3番目の数から1を引く → (0, 1, 1)
• 2番目と3番目の数から1を引く → (0, 0, 0)

このように、すべての数を0にするには合計7ステップ必要であることがわかります。

この問題へのアプローチ

この問題を効率的に解くポイントは、次の通りです。

• まず3つの数を入力として受け取ります。
• sort() 関数を使って、数値を昇順に並べ替えます。
• 最小の2つの数の合計が最大の数より小さい場合、その合計が答えになります（残りの数を0にしきれないため）。
• それ以外の場合は、1回の操作ごとに3つの数の合計が必ず2減るため、全体を0にするのに必要なステップ数は (a + b + c) ÷ 2 となります。

実装例

def maxScore(a: int, b: int, c: int):
   a, b, c = sorted((a, b, c))
   if a + b < c: return a + b
   return (a + b + c)//2
a=4
b=4
c=6
print(maxScore(a,b,c))     

上記のコードを実行すると、次の出力が得られます。

出力

7

入力 a=4、b=4、c=6 の場合、すべての数を0にするには7ステップかかるため、プログラムは正しく「7」を返します。このアルゴリズムはソートと簡単な条件分岐だけで構成されており、計算量も少なく実用的です。