Pythonで配列の全要素を等しくするための最小操作回数を求めるプログラム

問題の概要

値 n が与えられたとします。ここで、n 個の要素を持つ配列 nums を考えます。この配列は、すべてのインデックス i に対して arr[i] = (2*i)+1 と定義されます。つまり、[1, 3, 5, 7, ...] という奇数の連なりです。

1 回の操作では、0 <= x, y < n を満たす 2 つのインデックス x と y を自由に選び、nums[x] から 1 を引くと同時に nums[y] に 1 を加えることができます。この操作を繰り返して、配列内のすべての要素を同じ値に揃えたいのです。求めるのは、そのために必要な最小の操作回数です。

具体例

入力が n = 4 の場合を考えてみましょう。このとき初期状態の配列は [1, 3, 5, 7] であり、出力は 4 となります。

• 1 回目の操作後：[2, 3, 5, 6]
• 2 回目の操作後：[3, 3, 5, 5]
• 3 回目の操作後：[4, 3, 4, 5]
• 4 回目の操作後：[4, 4, 4, 4]（すべて等しくなった）

解き方のポイント

まず注目すべきは、配列の要素の合計は操作によって変わらないという点です。したがって、最終的な目標値は配列の平均値、すなわち n に固定されます。各操作は「大きい要素から小さい要素へ 1 を移す」行為なので、必要な最小操作回数は「平均値 n より小さい要素の不足分（n − 要素値）の総和」と一致します。

この考え方に基づき、以下の手順で答えを求めます。

• ans := 0 と初期化する

• n が 1 の場合は操作不要なので、ans を返す

• q := (n // 2) − 1 とする（平均未満の要素の個数に対応）

• j := 1 とする（平均未満の要素の値）

• q >= 0 の間、次を繰り返す：

  • ans := ans + (n − j)

  • q := q − 1

  • j := j + 2

• ans を返す

このアルゴリズムの計算量は O(n/2)、つまり O(n) となり、非常に効率的です。

Pythonでの実装例

def solve(n):
    ans = 0
    if n == 1:
        return ans
    q = (n // 2) - 1
    j = 1
    while q >= 0:
        ans = ans + (n - j)
        q -= 1
        j += 2
    return ans

n = 4
print(solve(n))

入力

4

出力

4

このように、平均値との差分に着目することで、シミュレーションを行わずとも最小操作回数を効率よく算出できます。