概要

\(N\) 人の子どもが持っているお菓子の個数を、最大値と最小値の差が \(1\) 以下になるまで平滑化するのに必要な操作回数を求める問題です。操作は「最も多い人から \(1\) 個回収し、最も少ない人に \(1\) 個渡す」という内容です。

考察

最終的な状態を特定する

お菓子の総数 \(S = \sum A_i\) は操作によって変化しません。最終的に全員の個数の差が \(1\) 以下になるということは、全員が「平均値に近い個数」を持つことになります。 具体的には、\(S\) を \(N\) で割った商を \(q\)、余りを \(r\) とすると、最終的なお菓子の分配は以下のようになります。 - \(q+1\) 個持っている子どもが \(r\) 人 - \(q\) 個持っている子どもが \(N-r\) 人

操作回数の性質

問題文にある通り、どの最大値・最小値のペアを選んで操作しても最終的な合計回数は変わりません。 「操作 \(1\) 回」につき、「目標より多く持っている人から \(1\) 個減り、目標より少なく持っている人に \(1\) 個増える」という変化が起きます。したがって、合計操作回数は「初期状態で目標より多く持っている分を、どれだけ削る必要があるか」の総和と一致します。

効率的な計算方法

愚直に \(1\) 個ずつ移動させるシミュレーションを行うと、お菓子の数 \(A_i\) が最大 \(10^9\) と非常に大きいため、実行時間制限に間に合いません。 そこで、初期状態の配列 \(A\) を昇順にソートし、最終的な状態（これも昇順に並べたもの）と比較することで、各個人が「最終的に何個持つべきか」を対応させることができます。

ソート後の \(A\) に対して、目標の状態 \(B\) を以下のように定めます。 - \(B_0, B_1, \dots, B_{N-r-1}\) は \(q\) 個 - \(B_{N-r}, \dots, B_{N-1}\) は \(q+1\) 個

このとき、合計操作回数は \(\sum_{i=0}^{N-1} \max(0, A_i - B_i)\) で求めることができます。

アルゴリズム

1. \(N\) 人のお菓子の総和 \(S\) を計算します。
2. 最終的な分配の基準となる \(q = S \text{ // } N\) と \(r = S \text{ \% } N\) を求めます。
3. 初期状態の配列 \(A\) を昇順にソートします。
4. ソートされた \(A\) の各要素 \(A_i\) について、目標の個数 \(B_i\) と比較します。
   • \(0 \le i < N-r\) のとき：目標は \(q\) 個。\(A_i > q\) ならば、その差分 \(A_i - q\) を答えに加算します。
   • \(N-r \le i < N\) のとき：目標は \(q+1\) 個。\(A_i > q+1\) ならば、その差分 \(A_i - (q+1)\) を答えに加算します。
5. 加算された合計値を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 配列のソートに \(O(N \log N)\) かかり、その後の総和計算やループは \(O(N)\) です。\(N \le 5 \times 10^5\) であるため、十分に高速です。
• 空間計算量: \(O(N)\)
  • 入力された配列 \(A\) を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 総和の型: \(N\) や \(A_i\) が大きいため、お菓子の総和 \(S\) や最終的な操作回数は 64 bit 整数（Pythonでは標準の整数型）で扱う必要があります。

• ソートの利用: どの \(A_i\) を \(q\) にし、どの \(A_i\) を \(q+1\) に割り当てるのが「操作回数」の定義に合うかを考える際、ソートして小さい順（または大きい順）に並べることで、過不足を正しく集計できるようになります。

  ソースコード

import sys

def solve():
    # 使用するメモリを最小限に抑えつつ、入力を高速に読み込むために sys.stdin.read().split() を使用します。
    # N は子どもの人数、A は各子どもが持っているお菓子の個数のリストです。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    a = list(map(int, input_data[1:]))
    
    # 子どもが1人の場合は操作を行わないため、0を出力して終了します。
    if n <= 1:
        print(0)
        return
    
    # お菓子の総数を計算します。
    total_candies = sum(a)
    
    # 最終的なお菓子の分配状態を計算します。
    # 全員が平均値に近い個数を持つようになります。
    # q は全員が最低限持つ個数、r はそれより1個多く持つ子どもの人数です。
    q = total_candies // n
    r = total_candies % n
    
    # 操作回数を最小化する（あるいは不変であることを利用する）ために、
    # 現在の個数リスト A をソートし、目標とする分配状態（ソート済み）と比較します。
    a.sort()
    
    # 最終的な状態 B (ソート済み) は以下のようになります。
    # - 最初の (n - r) 人が q 個持っている。
    # - 残りの r 人が q + 1 個持っている。
    
    # 操作の合計回数は、初期状態から目標状態へ移動させるお菓子の総数に等しく、
    # これは「目標より多く持っている子どもから回収するお菓子の総数」として計算できます。
    ans = 0
    
    # 最初の (n - r) 人の目標個数は q です。
    for i in range(n - r):
        if a[i] > q:
            ans += a[i] - q
            
    # 残りの r 人の目標個数は q + 1 です。
    for i in range(n - r, n):
        if a[i] > q + 1:
            ans += a[i] - (q + 1)
            
    # 合計の操作回数を出力します。
    print(ans)

if __name__ == '__main__':
    solve()

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