概要

\(N\) 人の子どもが持つケーキの個数を、隣り合う子ども同士の受け渡しのみで均等にするための最小操作回数を求める問題です。ケーキの総数が \(N\) で割り切れない場合は、均等に配ることが不可能なため -1 を出力します。

考察

1. 目標値の決定

まず、全員が最終的に持つべきケーキの数（目標値）を計算します。ケーキの総数を \(S\) とすると、一人あたりの個数は \(target = S / N\) となります。\(S\) が \(N\) で割り切れない場合、どのように動かしても均等にはできないため、即座に -1 と判定できます。

2. 境界をまたぐ移動に着目する

一列に並んだ子どもたちの間の「境界」に注目するのがこの問題のポイントです。 例えば、子ども \(1\) から子ども \(i\) までのグループ（左側のグループ）を考えます。このグループが元々持っているケーキの合計が、目標の合計（\(target \times i\)）よりも多い場合、その余剰分は必ず「子ども \(i\) と子ども \(i+1\) の間の境界」を越えて右側に送られなければなりません。逆に不足している場合は、右側から境界を越えて送られてくる必要があります。

3. 最小操作回数の導出

隣り合う \(2\) 人の間でケーキを \(1\) 個受け渡す操作は、ある境界をケーキが \(1\) つ通過することに対応します。 各境界 \(i\)（子ども \(i\) と \(i+1\) の間）において、そこを通過しなければならないケーキの個数は、「子ども \(1\) から \(i\) までが現在持っているケーキの総数」と「子ども \(1\) から \(i\) までが最終的に持つべきケーキの総数」の差の絶対値に一致します。

この「差の絶対値」をすべての境界（合計 \(N-1\) 箇所）について足し合わせたものが、求める最小操作回数となります。

アルゴリズム

1. ケーキの総和 total_cakes を計算する。
2. total_cakes % N != 0 ならば -1 を出力して終了する。
3. 目標値 target = total_cakes // N を計算する。
4. 変数 ans（合計操作回数）と current_diff（累積の過不足分）を \(0\) で初期化する。
5. 子ども \(i = 1\) から \(N-1\) まで以下を繰り返す：
   • current_diff に A[i] - target を加算する。
   • ans に abs(current_diff) を加算する。
6. 最終的な ans を出力する。

計算量

• 時間計算量: \(O(N)\)
  • ケーキの総和の計算と、リストを一巡するループがそれぞれ \(O(N)\) であるため、全体でも線形時間で動作します。
• 空間計算量: \(O(N)\)
  • 入力されたケーキの個数を格納する配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 累積和の考え方: 境界ごとの過不足を計算する際、毎回合計を出し直すと \(O(N^2)\) かかってしまいますが、前から順番に current_diff を更新していくことで \(O(N)\) で計算できます。

• 大きな数値への対応: ケーキの個数 \(A_i\) や \(N\) の値が大きいため、合計値や操作回数が 32bit 整数に収まらない可能性があります。Python では自動的に多倍長整数として扱われるため問題ありませんが、他の言語（C++など）では long long 型を使用する必要があります。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 子どもの数 N と各子どもが持つケーキの数 A を取得
    n = int(input_data[0])
    a = list(map(int, input_data[1:]))
    
    # ケーキの総数を計算
    total_cakes = sum(a)
    
    # 総数が N で割り切れない場合は、均等に分配できないため -1 を出力
    if total_cakes % n != 0:
        print("-1")
        return
    
    # 最終的に全員が持つべきケーキの数
    target = total_cakes // n
    
    ans = 0
    current_diff = 0
    # 隣り合う子ども同士の境界を越えて移動させるケーキの数を計算
    # 累積和の絶対値の合計が最小操作回数となる
    for i in range(n - 1):
        # 現在の子どもまでの過不足分を累積
        current_diff += a[i] - target
        # その過不足分を解消するために境界を越えるケーキの移動回数を加算
        ans += abs(current_diff)
        
    print(ans)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。