概要

荷物列を順番を崩さずにいくつかの連続区間に分割し、各区間（各荷台）の総重量がすべて等しくなるようにするとき、使える荷台の個数の最大値を求めます。

考察

重要な気づき

荷台の個数を \(k\) 個とすると、各荷台の総重量は - 全体の総和を \(T=\sum H_i\) として - 各荷台の重さ \(S = T/k\)

となる必要があります。よって \(k\) は \(T\) の約数でなければなりません。

さらに、荷物は連続区間で分けるので、区切り位置は「累積和」で表せます。
累積和を \(P_0=0,\,P_i=H_1+\cdots+H_i\) とすると、重さ \(S\) の区間を \(k\) 個作るには

• \(S, 2S, 3S, \ldots, (k-1)S\)

がすべて累積和集合 \(\{P_0,P_1,\ldots,P_N\}\) の中に存在することが必要十分です。
（これらが存在すれば、その位置で区切ることで各区間和がすべて \(S\) になります。）

また、どの区間にも少なくとも1個の荷物が入るので \(k \le N\)。
加えて、各区間和 \(S\) は最大の荷物重量 \(\max(H_i)\) 以上でないと不可能なので - \(S \ge \max(H_i)\) - つまり \(T/k \ge \max(H_i) \Rightarrow k \le T/\max(H_i)\)

が成り立ちます。

以上より、調べるべき \(k\) は - \(k \mid T\) - \(k \le \min\!\left(N,\left\lfloor T/\max(H_i)\right\rfloor\right)\)

に絞れます。

素朴解が厳しい理由

「\(k\) を大きい方から順に全探索」して毎回配列を走査すると、最悪で \(O(N^2)\) 近くになり間に合いません。
そこで、 - 候補の \(k\) を「\(T\) の約数」に限定（数が少ない） - 判定は走査ではなく「累積和の集合に含まれるか」を見る（1回の判定が軽い）

という方針にします。

アルゴリズム

1. 全体和 \(T=\sum H_i\) と最大値 \(M=\max(H_i)\) を求める。
2. 累積和 \(P_i\) を作り、すべてを集合 pref に入れる（0 も入れる）。
3. \(T\) を素因数分解し、全約数を列挙する。
4. 約数のうち \(k \le k_{\max}=\min(N,\lfloor T/M\rfloor)\) を満たすものだけ候補にし、大きい順に試す。
5. 候補 \(k\) について \(S=T/k\) とし、S, 2S, ..., (k-1)S がすべて pref に含まれるかを集合検索で確認する。
   • すべて含まれれば、その \(k\) が最大なので出力して終了。
6. どれもダメなら必ず \(k=1\) は可能なので 1 を出力。

（例） - \(H=[1,2,3,3,2,1]\) なら \(T=12\)。 - \(k=4\) のとき \(S=3\)。累積和は \(0,1,3,6,9,11,12\) なので \(3,6,9\) が存在しOK → 4分割可能。

計算量

• 時間計算量:
  
  • 素因数分解: \(O(\sqrt{T})\)
    
  • 累積和作成: \(O(N)\)
    
  • 約数個数を \(d\) とすると、判定は合計で概ね \(O\!\left(\sum_{k\in \text{candidates}} k\right)\)（各候補 \(k\) につき最大 \(k-1\) 回の集合検索）
    
  • まとめて \(O(\sqrt{T}+N+\sum k)\)
• 空間計算量: \(O(N)\)（累積和集合）

実装のポイント

• 累積和を set に入れることで、「区切り位置が存在するか」を \(O(1)\) 平均で判定できます。

• 先に \(k_{\max}=\min(N,\lfloor T/\max(H_i)\rfloor)\) で候補を絞ると無駄な試行が減ります。

• 約数は大きい順に試し、最初に成功したものを出力すれば「最大個数」が保証されます。

• 入力が大きいので sys.stdin.buffer.read() で高速に読みます。

  ソースコード

import sys
import math


def factorize(n: int):
    factors = []
    cnt = 0
    while n % 2 == 0:
        n //= 2
        cnt += 1
    if cnt:
        factors.append((2, cnt))
    p = 3
    while p * p <= n:
        if n % p == 0:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            factors.append((p, cnt))
        p += 2
    if n > 1:
        factors.append((n, 1))
    return factors


def all_divisors_from_factors(factors):
    divs = [1]
    for p, e in factors:
        cur = []
        pe = 1
        for _ in range(e + 1):
            for d in divs:
                cur.append(d * pe)
            pe *= p
        divs = cur
    return divs


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    H = data[1:]

    total = sum(H)
    max_h = max(H)

    pref = set()
    s = 0
    pref.add(0)
    for h in H:
        s += h
        pref.add(s)

    kmax = min(N, total // max_h)  # S = total/k must satisfy S >= max_h
    factors = factorize(total)
    divs = all_divisors_from_factors(factors)

    candidates = [k for k in divs if k <= kmax]
    candidates.sort(reverse=True)

    for k in candidates:
        seg = total // k
        if seg < max_h:
            continue
        x = seg
        ok = True
        for _ in range(k - 1):
            if x not in pref:
                ok = False
                break
            x += seg
        if ok:
            print(k)
            return

    print(1)


if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。