概要

\(N\) 人の子どもが持つお菓子を「最大と最小の差が \(1\) 以下」になるまで均す操作の回数を求める問題です。最終状態を直接計算し、そこへ到達するのに必要な操作回数を求めます。

考察

最終状態はどうなるか？

お菓子の総数 \(S = \sum A_i\) は操作を通じて変わりません。最終状態ではどの2人の差も \(1\) 以下なので、\(q = \lfloor S/N \rfloor\)、\(r = S \bmod N\) とすると：

• \(N - r\) 人が \(q\) 個を持つ
• \(r\) 人が \(q + 1\) 個を持つ

という状態に必ずなります。

操作回数はどう数えるか？

1 回の操作で「最大の子から 1 個減らし、最小の子に 1 個増やす」ので、操作回数は 目標より多く持っている子から回収するお菓子の総数 に等しくなります（回収した分がそのまま不足している子に渡される）。

素朴なシミュレーションがダメな理由

\(A_i\) が最大 \(10^9\) なので、1 個ずつ移す操作を愚直にシミュレーションすると、操作回数が膨大（最悪 \(O(N \times 10^9)\) 程度）になり TLE します。

最適な割り当てを考える

ソートした \(A\) に対して、ソートした目標値を割り当てれば、各子どもが「目標からどれだけずれているか」を直接計算できます。具体的には、\(A\) を昇順にソートし、小さい方から \(N - r\) 人に目標 \(q\) を、残り \(r\) 人に目標 \(q + 1\) を割り当てます。

具体例: \(N = 4\), \(A = [1, 8, 3, 4]\) → \(S = 16\), \(q = 4\), \(r = 0\)

• ソート後: \([1, 3, 4, 8]\)
• 目標: \([4, 4, 4, 4]\)
• 差分: \([-3, -1, 0, +4]\)
• 超過分の合計: \(4\) → 答えは \(4\)

アルゴリズム

1. \(S = \sum A_i\) を求め、\(q = \lfloor S/N \rfloor\), \(r = S \bmod N\) を計算する。
2. \(A\) を昇順にソートする。
3. ソートした \(A\) の先頭 \(N - r\) 個に目標 \(q\) を、残り \(r\) 個に目標 \(q + 1\) を割り当てる。
4. \(A_i\) が目標を超えている部分の合計 \(\sum \max(A_i - \text{target}_i, 0)\) を求める。これが答え。

計算量

• 時間計算量: \(O(N \log N)\)（ソートがボトルネック）
• 空間計算量: \(O(N)\)（配列の保持）

実装のポイント

• \(A_i\) が最大 \(10^9\)、\(N\) が最大 \(5 \times 10^5\) なので、答えは非常に大きくなりうる。64 bit 整数（Python では自動対応）を使う。

• 目標を超えている分の合計 だけ を足せばよい（不足分の合計と一致するため、どちらか片方で OK）。

• sys.stdin.buffer.read() を使うことで大量入力を高速に処理している。

  ソースコード

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    A = [int(data[i + 1]) for i in range(N)]
    
    S = sum(A)
    q, r = divmod(S, N)
    
    # Sort A in non-decreasing order
    A.sort()
    
    # Sorted targets: first (N - r) children get q, last r children get q + 1
    ans = 0
    for i in range(N):
        if i < N - r:
            target = q
        else:
            target = q + 1
        if A[i] > target:
            ans += A[i] - target
    
    print(ans)

solve()

---

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