概要

一列に並んだ子どもたちに、隣同士のケーキ受け渡しだけで全員のケーキ数を均等にするとき、最小操作回数を求める問題です。これは「累積和の絶対値の総和」という有名な手法で効率的に解けます。

考察

重要な気づき：隣接間の「流量」に注目する

まず、すべての子どもが最終的に持つべきケーキの数は \(\text{target} = \frac{\sum A_i}{N}\) です。これが整数でなければ不可能なので -1 を出力します。

次に、子ども \(i\) と子ども \(i+1\) の間を流れるケーキの量（流量）を \(f_i\) とします。\(f_i > 0\) なら左から右へ、\(f_i < 0\) なら右から左へケーキが流れると考えます。

子ども \(1\) について考えると、子ども \(1\) が最終的に target 個になるためには、右隣との間で \(A_1 - \text{target}\) 個のケーキを右に送り出す必要があります。つまり：

\[f_1 = A_1 - \text{target}\]

同様に、子ども \(2\) は左から \(f_1\) 個受け取り、右に \(f_2\) 個送り出します。子ども \(2\) のバランスから：

\[A_2 + f_1 - f_2 = \text{target} \implies f_2 = (A_1 - \text{target}) + (A_2 - \text{target})\]

一般化すると、位置 \(i\) と \(i+1\) の間の流量は：

\[f_i = \sum_{j=1}^{i} (A_j - \text{target})\]

つまり、\(f_i\) は差分 \(A_j - \text{target}\) の累積和（prefix sum） です。

なぜ操作回数は \(|f_i|\) の総和か？

1回の操作は「隣接する2人の間でケーキを1個移動」なので、位置 \(i\) と \(i+1\) の間を通過するケーキの数は \(|f_i|\) 個です。各境界での通過量の合計が、全体の操作回数の最小値になります。

具体例

\(N = 4\), \(A = [7, 3, 1, 5]\) の場合、\(\text{target} = 16 / 4 = 4\) です。

| 位置 \(i\) | \(A_i - \text{target}\) | 累積和 \(f_i\) | \(|f_i|\) |

1	\(+3\)	\(3\)	\(3\)
2	\(-1\)	\(2\)	\(2\)
3	\(-3\)	\(-1\)	\(1\)
4	\(+1\)	\(0\)	\(0\)

答えは \(3 + 2 + 1 + 0 = 6\) 回です。（最後の累積和は必ず \(0\) になります。）

アルゴリズム

1. ケーキの総数 \(\sum A_i\) が \(N\) で割り切れなければ -1 を出力。
2. \(\text{target} = \frac{\sum A_i}{N}\) を計算。
3. \(B_i = A_i - \text{target}\) とし、\(B_i\) の累積和 \(S_i = \sum_{j=1}^{i} B_j\) を計算。
4. 答えは \(\sum_{i=1}^{N} |S_i|\)。

計算量

• 時間計算量: \(O(N)\)（配列を1回走査するだけ）
• 空間計算量: \(O(N)\)（入力配列の格納。累積和は変数1つで管理可能なので追加は \(O(1)\)）

実装のポイント

• 累積和を配列として保持する必要はなく、変数 prefix を更新しながら abs(prefix) を足し込めばよい。

• \(A_i\) が最大 \(10^9\)、\(N\) が最大 \(2 \times 10^5\) なので、累積和や操作回数は最大で約 \(2 \times 10^{14}\) 程度になりうる。Python は多倍長整数なのでオーバーフローの心配は不要だが、C++ などでは long long を使う必要がある。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    A = [int(input_data[i + 1]) for i in range(N)]
    
    total = sum(A)
    if total % N != 0:
        print(-1)
        return
    
    target = total // N
    
    # The minimum number of operations is the sum of absolute values of prefix sums of (A_i - target).
    # This is because the flow between position i and i+1 equals the prefix sum up to i.
    ops = 0
    prefix = 0
    for i in range(N):
        prefix += A[i] - target
        ops += abs(prefix)
    
    print(ops)

main()

---

この解説は claude4.6opus-thinking によって生成されました。