概要

連続した荷物をグループに分けて、各グループの合計重量が等しくなるように分配するとき、最大で何個のグループに分けられるかを求める問題。

考察

この問題では、荷物を連続した部分列に分割し、各部分列の和が等しくなるようにしなければなりません。また、そのような分割の最大数を求めたいです。

まず、すべてのグループの和が等しい値であるとすると、それは全体の和 \(S\) の約数でなければなりません。つまり、もし \(d\) 個のグループに分割するなら、各グループの和は \(S/d\) でなければいけません。

したがって、考えられるグループ数は、\(S\) の約数のうち、大きい方から順に試していけばよいです。なぜなら、グループ数が多くなるほど各グループの和が小さくなるので、最大の約数から順にチェックすれば最初に見つけたものが答えになります。

ナイーブな方法（例えば、すべての区切り方を試す）では、計算量が非常に大きくなり、間に合いません。しかし、約数の個数は \(S\) が最大 \(2 \times 10^{14}\) 程度でも高々数百程度なので、十分高速に処理できます。

各約数 \(d\) に対して、実際に分割が可能かどうかをシミュレーションします。つまり、前から順に足していき、和が \(S/d\) になったらカウントし、それ以上にならないよう注意しながら確認します。

アルゴリズム

1. 全体の和 \(S\) を求める。
2. \(S\) のすべての約数を求める（\(\sqrt{S}\) までの試し割りでOK）。
3. 約数を大きい順にソートする。
4. 各約数 \(d\) に対して、以下を試す：
   • 各グループの目標和：target = S / d
   • 左端から順に和を取っていき、target に達したらリセット。
   • 和が target を超えたら不可能。
   • 最終的に d グループちょうど作れていればそれが答え。
5. 最初に条件を満たした \(d\) を出力する。

計算量

• 時間計算量: \(O(\sqrt{S} + N \cdot d_{\text{max}})\)
  
  • 約数列挙に \(O(\sqrt{S})\)、各約数に対するシミュレーションに最悪 \(O(N)\) をかける。
• 空間計算量: \(O(\sqrt{S})\)
  
  • 約数を保存するリストのサイズ。

実装のポイント

• 約数は \(\sqrt{S}\) までのループで効率よく求められる。
• 約数を降順にソートして、最大の候補から順に試すことで、初めて条件を満たした時点で即時リターンできる。
• 各シミュレーションでは、現在の和が目標を超えないように注意しながら、グループ数が一致するか確認する。

## ソースコード

```python
import sys
import math

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    H = list(map(int, data[1:N+1]))
    
    total = sum(H)
    if N == 1:
        print(1)
        return
    
    # 約数を大きい順に試す
    divisors = []
    for i in range(1, int(math.sqrt(total)) + 1):
        if total % i == 0:
            divisors.append(i)
            if i != total // i:
                divisors.append(total // i)
    
    divisors.sort(reverse=True)
    
    # 各約数について、分割可能かチェック
    for d in divisors:
        target = total // d
        count = 0
        current_sum = 0
        i = 0
        while i < N:
            current_sum += H[i]
            if current_sum == target:
                count += 1
                current_sum = 0
            elif current_sum > target:
                break
            i += 1
        if current_sum == 0 and count == d:
            print(d)
            return

if __name__ == "__main__":
    main()

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