概要

一列に並んだ荷物を、順番を変えずにいくつかのグループ（荷台）に分け、各グループの合計重量をすべて等しくしたとき、最大で何個のグループに分割できるかを求める問題です。

考察

1. 累積和の活用

荷物を連続したグループに分けるとき、各グループの合計重量が \(w\) であるとします。 このとき、左から数えたグループの区切り目における「荷物の総重量（累積和）」は、必ず \(w, 2w, 3w, \dots, kw\)（ただし \(kw\) は全荷物の総重量 \(S\)）という値になります。

例えば、重さが \([1, 2, 1, 1, 1]\) の荷物があり、各グループの重量を \(w=3\) にすると決めた場合： - 累積和は \([1, 3, 4, 5, 6]\) です。 - 区切り目の累積和は \(3, 6\) となり、これらは累積和のリストの中に存在します。

2. 各グループの重量 \(w\) の候補

荷台の数 \(k\) を最大化するためには、各グループの重量 \(w\) をできるだけ小さくする必要があります。 \(w\) としてあり得る値は、「左から数個の荷物をまとめたときの合計重量」に限られます。つまり、累積和のリストに含まれる \(N\) 個の値のいずれかが \(w\) の候補となります。

3. 効率的な判定

ある \(w\) が条件を満たすかどうかを判定するには、以下の2点を確認します。 1. 全体の総重量 \(S\) が \(w\) で割り切れること（\(k = S/w\) が整数になる）。 2. \(2w, 3w, \dots, (k-1)w\) という値が、すべて累積和のリストの中に存在すること。

累積和のリストを set（集合型）に格納しておくことで、特定の値が存在するかどうかの判定を \(O(1)\) で高速に行うことができます。

アルゴリズム

1. 荷物の重さの累積和を計算し、リスト prefix_sum と集合 p_set に格納する。
2. 全荷物の総重量を \(S\) とする。
3. prefix_sum の各要素 \(w\) を小さい順に（左から順に）調べ、以下の処理を行う：
   • \(S\) が \(w\) で割り切れない場合は、次の \(w\) へ。
   • \(S\) が \(w\) で割り切れる場合、\(k = S/w\) とする。
   • \(j = 2, 3, \dots, k-1\) について、\(j \times w\) が p_set に含まれているか確認する。
   • すべて含まれていれば、その時の \(k\) が最大値となるため、出力して終了する。

計算量

• 時間計算量: \(O(N \log N)\)
  • 累積和の計算と集合への格納に \(O(N)\) かかります。
  • ループ内での判定回数は、最悪の場合（すべての荷物の重さが \(1\) のときなど）でも、調和級数の和の性質から \(O(N/1 + N/2 + \dots + N/N) = O(N \log N)\) となり、十分に高速です。
• 空間計算量: \(O(N)\)
  • 累積和を保持するためのリストと集合に \(O(N)\) のメモリを使用します。

実装のポイント

• 最小の \(w\) から試す: prefix_sum は必ず昇順になっているため、リストの先頭から順に試すことで、最初に見つかった「条件を満たす \(w\)」が、最も大きいグループ数 \(k\) を与えることになります。

• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と大きいため、sys.stdin.read().split() などを用いて入力を一括で取得すると実行時間を短縮できます。

• 早期終了: 条件を満たす \(w\) が見つかった瞬間に計算を終了して結果を出力することで、無駄な探索を省いています。

  ソースコード

import sys

# 競技プログラミングにおける標準的な高速入力処理
def solve():
    # 全ての入力を一度に読み込み、スペース区切りでリスト化する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 荷物の個数 N
    n = int(input_data[0])
    # 各荷物の重さ Hi
    h = list(map(int, input_data[1:]))
    
    # 累積和を計算する
    # prefix_sum[i] は左から i+1 番目までの荷物の総重量を表す
    prefix_sum = [0] * n
    current_sum = 0
    for i in range(n):
        current_sum += h[i]
        prefix_sum[i] = current_sum
    
    # 全荷物の総重量 S
    total_sum = prefix_sum[-1]
    
    # 累積和の値を集合（set）に格納し、O(1) での検索を可能にする
    p_set = set(prefix_sum)
    
    # 使用できる荷台の個数を最大化するためには、各荷台の重量 w を最小化すればよい
    # 各荷台の重量 w は、必ずいずれかの累積和の値（prefix_sum[i]）と一致する必要がある
    # また、w は総重量 total_sum の約数でなければならない
    
    # 累積和は昇順に並んでいるため、順番に w として試すことで
    # 最初に見つかった有効な w が、荷台の個数 k = total_sum / w を最大化する
    for w in prefix_sum:
        # w が総重量を割り切れる場合のみ、均等な荷分けの可能性がある
        if total_sum % w == 0:
            k = total_sum // w
            
            # 荷台の個数 k は荷物の個数 n を超えることはできない
            if k > n:
                continue
            
            # 各荷台の重量が w であるとき、累積和の中に w, 2w, 3w, ..., kw が
            # すべて存在すれば、連続する荷物を組み合わせて重量 w のグループを k 個作ることができる
            # w と kw (= total_sum) は既に存在することが分かっているため、
            # 2w から (k-1)w までが累積和に含まれているかを確認する
            is_valid = True
            for j in range(2, k):
                if (j * w) not in p_set:
                    is_valid = False
                    break
            
            # 条件を満たす最小の w が見つかったら、その時の k を出力して終了
            if is_valid:
                print(k)
                return

if __name__ == '__main__':
    solve()

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