概要

隣同士でケーキを1個ずつ移動できるとき、全員のケーキ数を同じにするための最小操作回数を求める問題です（不可能なら -1）。

考察

まず、最終的に全員が同じ個数 \(x\) を持つには、総数 \(S=\sum A_i\) が \(N\) で割り切れて \(x=\frac{S}{N}\) となる必要があります。これが成り立たない場合は絶対に実現できないので -1 です。

次に「最小回数」を考えます。素朴に「多い人から少ない人へ近いところに配る」などをシミュレーションすると、移動の順序によって状態が複雑に変わったり、1個ずつ動かすため操作回数が最大で非常に大きく（\(10^{14}\) など）なり得て、直接の操作シミュレーションは現実的ではありません。

重要な観察は次です：

• 子ども \(i\) と \(i+1\) の間（境界）をまたいで何個ケーキを移動させる必要があるかは、最終状態が決まれば一意に決まる
  
• その「境界をまたぐ必要移動量」の絶対値の合計が、最小操作回数になる（1回の操作は境界をまたいで1個動かすことに対応）

ここで、左から順に「いままでの過不足」を考えます。
平均との差 \(A_i-\text{avg}\) を足し合わせた $\( \text{running}_i = \sum_{k=1}^{i} (A_k-\text{avg}) \)\( は、「子ども \)1..i$ の範囲が、最終的に必要な個数に対して何個多い（正）/足りない（負）か」を表します。

すると境界 \((i,i+1)\) をまたいで動かすべき個数はちょうど \(\text{running}_i\) 個であり、必要操作回数は \(|\text{running}_i|\) 回になります。よって答えは $\( \sum_{i=1}^{N-1} |\text{running}_i| \)\( です（最後の境界は存在しないので \)N-1$ 個分）。

具体例

例えば \(N=4,\ A=[1,6,2,3]\) だと総数は \(12\)、平均は \(\text{avg}=3\)。

• \(i=1\): running \(=1-3=-2\) → 境界(1,2)をまたいで2個右から左へ必要 → \(2\) 回
• \(i=2\): running \(=-2+(6-3)=1\) → 境界(2,3)をまたいで1個左から右へ必要 → \(1\) 回
• \(i=3\): running \(=1+(2-3)=0\) → 境界(3,4)は \(0\) 回

合計 \(2+1+0=3\) 回が最小です。

アルゴリズム

1. \(S=\sum A_i\) を計算し、\(S \bmod N \neq 0\) なら -1 を出力して終了
2. \(\text{avg}=S/N\) を求める
3. running = 0, ans = 0 として、\(i=1..N-1\)（0-indexなら range(N-1)）について
   • running += A[i] - avg
   • ans += abs(running)
4. ans を出力

この running は各境界を越える必要移動量そのもので、各境界は独立に「必要なぶんだけ」移動させればよいので、合計が最小操作回数になります。

計算量

• 時間計算量: \(O(N)\)（1回の走査で完了）
• 空間計算量: \(O(1)\)（入力配列以外は定数個の変数）

実装のポイント

• ループは \(i=1..N-1\)（最後の子どもの右側には境界がない）までで十分です。

• ans は大きくなり得ます（\(N\) が大きく、差も大きい場合）ので、Pythonでは問題ありませんが、他言語なら 64bit 整数（long long など）を使います。

• 入力が大きいので sys.stdin.buffer.read() のような高速入力が有効です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N = data[0]
    A = data[1:1+N]

    total = sum(A)
    if total % N != 0:
        print(-1)
        return

    avg = total // N
    running = 0
    ans = 0
    for i in range(N - 1):
        running += A[i] - avg
        ans += abs(running)

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。