概要

連続する荷物をグループに分け、各グループの重量が等しくなるようにするとき、作れるグループ（荷台）の最大数を求める問題です。

考察

重要な気づき①：荷台の数は総重量の約数

荷台を \(k\) 個使うとき、各荷台の重量は \(\frac{\text{総重量}}{k}\) になります。これが整数でなければ等分できないため、荷台の数 \(k\) は総重量の約数でなければならないことがわかります。

重要な気づき②：貪欲に分割できる

各荷台の目標重量が決まれば、左から順番に荷物を見ていき、累積和が目標重量に達したらそこで区切る、という貪欲法で判定できます。

例えば、\(H = [2, 1, 3, 2, 4]\)（総重量 \(12\)）の場合： - \(k = 4\) のとき、目標重量は \(3\) - \(2 + 1 = 3\) ✓（1つ目の荷台） - \(3 = 3\) ✓（2つ目の荷台） - \(2\) のあと \(2 + 4 = 6 > 3\) で失敗 ✗ - \(k = 3\) のとき、目標重量は \(4\) - \(2 + 1 = 3 < 4\)、\(2 + 1 + 3 = 6 > 4\) で失敗 ✗ - \(k = 2\) のとき、目標重量は \(6\) - \(2 + 1 + 3 = 6\) ✓（1つ目の荷台） - \(2 + 4 = 6\) ✓（2つ目の荷台） - 成功！答えは \(2\)

素朴なアプローチの問題点

全ての分割パターンを試すと指数的な計算量になりますが、約数のみを試せばよいことと、各約数に対する判定が \(O(N)\) でできることから、効率的に解けます。

アルゴリズム

1. 総重量の約数を列挙する

   • \(1\) から \(\sqrt{\text{総重量}}\) まで調べ、約数のペアを全て列挙

2. 約数を降順にソートする

   • 荷台の数を最大化したいので、大きい約数から試す

3. 各約数 \(k\) について分割可能か判定する

   • 目標重量 \(= \frac{\text{総重量}}{k}\)
   • 左から順に荷物を足していき：
     • 累積和が目標重量と一致したら、荷台1つ完成（累積和をリセット）
     • 累積和が目標重量を超えたら、失敗
   • 最後まで走査して、ちょうど \(k\) 個の荷台ができたら成功

4. 最初に成功した \(k\) を出力する

計算量

• 時間計算量: \(O(\sqrt{S} + d(S) \cdot N)\)

  • \(S\) は総重量、\(d(S)\) は \(S\) の約数の個数
  • 約数の列挙に \(O(\sqrt{S})\)
  • 各約数について \(O(N)\) で判定
  • 約数の個数は \(S \leq 2 \times 10^{14}\) でも高々数千程度なので十分高速

• 空間計算量: \(O(N + d(S))\)

  • 入力配列と約数リストの保持

実装のポイント

• 約数の列挙: \(i \times i \leq \text{total}\) の範囲で探索し、\(i\) と \(\frac{\text{total}}{i}\) の両方を追加する（ただし重複に注意）

• 判定の終了条件: ループ終了後に current == 0 かつ count == k であることを確認する

• 最悪ケースの保証: 必ず \(k = 1\)（全部を1つの荷台に載せる）は成功するので、答えが存在しないケースはない

  ソースコード

def solve():
    N = int(input())
    H = list(map(int, input().split()))
    
    total = sum(H)
    
    # 累積和を計算
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + H[i]
    
    # 荷台の数kを大きい方から試す
    # kが総和の約数である必要がある
    # 各荷台の重量は total / k
    
    # 総和の約数を列挙
    divisors = []
    i = 1
    while i * i <= total:
        if total % i == 0:
            divisors.append(i)
            if i != total // i:
                divisors.append(total // i)
        i += 1
    
    # 約数を降順にソート（大きい荷台数から試す）
    divisors.sort(reverse=True)
    
    for k in divisors:
        # 各荷台の重量
        target = total // k
        
        # 連続する荷物でtargetを作れるか確認
        count = 0
        current = 0
        possible = True
        
        for i in range(N):
            current += H[i]
            if current == target:
                count += 1
                current = 0
            elif current > target:
                possible = False
                break
        
        if possible and current == 0 and count == k:
            print(k)
            return
    
    # 少なくとも1つの荷台には全部載せられる
    print(1)

solve()

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