Pythonで配列を厳密に増加させるための最小操作回数を求めるプログラム

問題の概要

配列 nums が与えられているとします。1回の操作では、配列内の任意の要素を1つ選び、その値を1だけ増やすことができます。例えば、[4,5,6] という配列でインデックス1の要素に対して操作を行うと、[4,6,6] になります。

このとき、nums を厳密に増加する配列(すべての要素が直前の要素よりも必ず大きい状態)にするために必要な、最小の操作回数を求めるのが目的です。

例えば、入力が nums = [8,5,7] の場合、出力は 7 になります。これは次のような手順で要素を増やしていく必要があるためです。

[8,6,7] → [8,7,7] → [8,8,7] → [8,9,7] → [8,9,8] → [8,9,9] → [8,9,10]

解法のアルゴリズム

この問題は、配列を左から順に走査し、隣り合う要素同士を比較することで効率的に解けます。手順は以下の通りです。

• カウンタ count を 0 で初期化します。
• i を 0 から配列サイズ - 2 まで繰り返します。
• もし nums[i+1] <= nums[i](次の要素が現在の要素以下)であれば:
• count に nums[i] - nums[i+1] + 1 を加算します。
• nums[i+1] を nums[i] + 1 になるよう更新します。

最後に count を返せば、それが最小の操作回数となります。

Pythonでの実装例

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

def solve(nums):
    count = 0
    for i in range(len(nums)-1):
        if nums[i+1] <= nums[i]:
            count += nums[i]-nums[i+1]+1
            nums[i+1] += nums[i]-nums[i+1]+1
    return count

nums = [8,5,7]
print(solve(nums))

入力

[8,5,7]

出力

7

解説

このアルゴリズムのポイントは、現在の要素が前の要素以下だった場合に、前の要素よりちょうど1大きい値まで一気に引き上げる点です。このとき必要な増加量は nums[i] - nums[i+1] + 1 回であり、これをカウントに累積していきます。

上記の例では、まず 5 を 9 にするのに4回、次に 7 を 10 にするのに3回の操作が必要となり、合計7回という結果になります。計算量は O(n) と非常に効率的で、大きな配列でも高速に動作します。