概要

隣接する子ども同士でケーキをやりとりして、全員のケーキの個数を等しくするための最小操作回数を求めます。ただし、ケーキの総数が人数で割り切れない場合は -1 を出力します。

考察

まず、ケーキの総数 \(S = \sum_{i=1}^{N} A_i\) が \(N\) で割り切れないと、全員に同じ数を配ることは不可能です。そのため、その場合は -1 を出力します。

割り切れる場合、目標となる個数は \(\text{target} = S / N\) です。

素朴なアプローチとして、「余っている人から足りない人に向かって一つずつ移動させる」と考えると、計算量が多くなり、間に合いません。また、移動経路を最適化するのも難しいです。

ここで重要な観察があります：
「操作は隣接する二人の間でのみ行われる」ということは、全体の「流れ」を考えると、ある地点までの累積的な過不足の量が重要になります。

つまり、左から \(i\) 番目までの範囲に含まれるケーキの総和が、目標値 \(\text{target} \times (i+1)\) よりどれだけ多いか少ないかを計算すると、そこまでの範囲で「右側にどれだけ流れる必要があるか（または左から流れてくるべきか）」がわかります。

例えば、左から累積的に見て、ある位置で余りが \(+3\) であれば、そこから右に向かって合計3個のケーキを運び出す必要があります。この値（絶対値）をすべての位置について足し合わせたものが、必要な最小操作回数になります。

このように、累積の差分の絶対値の和を取ることで効率よく答えを求めることができます。

アルゴリズム

1. ケーキの総和 \(S\) を求め、\(N\) で割り切れるか確認する。割り切れなければ -1 を出力して終了。
2. 目標値 \(\text{target} = S / N\) を求める。
3. 左から順に累積の差分 \(B[i] = \sum_{j=0}^{i} A[j] - \text{target} \times (i+1)\) を計算していく。
4. 各 \(i\) に対して \(|B[i]|\) を足し合わせたものが答えとなる。
5. 最後の要素は自動的に決まるので、計算は \(i = 0\) から \(N-2\) までで十分。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （累積変数のみを使用）

実装のポイント

• cum_diff という変数で累積の差分を管理し、毎回 abs(cum_diff) を結果に加算することで効率的に計算できます。
• 最後の要素は他のすべての要素が決まれば自動的に一致するため、ループは N-1 回で十分です。
• 入力を高速に読み込むために sys.stdin.read を使用しています。

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    A = list(map(int, data[1:N+1]))
    
    total = sum(A)
    
    if total % N != 0:
        print(-1)
        return
    
    target = total // N
    
    # 累積の不足/余剰を計算
    # B[i] = A[0] + ... + A[i] - target*(i+1)
    # この値は、左からi番目までの範囲で、targetよりどれだけ多く持っているか（正）または足りないか（負）を示す
    cum_diff = 0
    res = 0
    for i in range(N - 1):  # 最後の人は自動的に決まるのでN-1まで
        cum_diff += A[i] - target
        res += abs(cum_diff)
    
    print(res)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。