概要

\(N\) 個の荷物を、積載上限 \(C\) のエレベーターで運ぶ最小往復回数を求める問題です。これは「ビンパッキング問題」の一種で、ビット全探索とDPを組み合わせて解きます。

考察

問題の本質

• 荷物を「重さの合計が \(C\) 以下」のグループに分けたい
• グループ数（= 往復回数）を最小化したい

素朴なアプローチ

全ての分け方を試すと、\(N\) 個の荷物を分割する方法は「ベル数」と呼ばれ、\(N = 15\) では約 \(10^9\) 通りになりTLEします。

重要な気づき

\(N \leq 15\) という制約に注目します。\(2^{15} = 32768\) なので、荷物の選び方（部分集合）をビットマスクで表現できます。

例えば \(N = 3\) のとき： - 101（2進数）= 荷物1と荷物3を選んだ状態 - 111 = 全ての荷物を選んだ状態

解法の方針

「どの荷物を運び終えたか」を状態としてDPします。

• dp[mask] = mask で表される荷物を全て運ぶのに必要な最小往復回数

遷移は「まだ運んでいない荷物の中から、重さ \(C\) 以下の組み合わせを選んで1回で運ぶ」です。

アルゴリズム

1. 前処理: 全ての部分集合 \(2^N\) 通りについて、重さの合計を計算しておく

2. DP初期化: dp[0] = 0（何も運んでいない状態は0回）、他は \(\infty\)

3. DP遷移: 各状態 mask について

   • 残りの荷物 remaining = 全体 XOR mask を求める
   • remaining の部分集合 sub を列挙
   • sub の重さが \(C\) 以下なら、dp[mask | sub] = min(dp[mask | sub], dp[mask] + 1)

4. 答え: dp[(1 << N) - 1]（全荷物を運んだ状態）

部分集合の列挙テクニック

ある集合 remaining の全ての空でない部分集合は、以下のループで \(O(2^{|remaining|})\) で列挙できます：

sub = remaining
while sub > 0:
    # sub を処理
    sub = (sub - 1) & remaining

計算量

• 時間計算量: \(O(3^N)\)

  • 状態数は \(2^N\)、各状態から遷移する部分集合の総数は \(\sum_{k=0}^{N} \binom{N}{k} 2^{N-k} = 3^N\)

• 空間計算量: \(O(2^N)\)

  • dp 配列と subset_weight 配列にそれぞれ \(2^N\) 要素

\(N = 15\) のとき、\(3^{15} \approx 1.4 \times 10^7\) なので十分間に合います。

実装のポイント

1. 事前に重さを計算: 毎回部分集合の重さを計算すると遅くなるため、subset_weight[mask] を前もって計算

2. 部分集合列挙の公式: sub = (sub - 1) & remaining は競プロでよく使うテクニック。remaining のビットが立っている位置の部分集合だけを効率的に列挙できる

3. INFの扱い: 到達不可能な状態からは遷移しないように if dp[mask] == INF: continue でスキップ

   ソースコード

def solve():
    N, C = map(int, input().split())
    W = list(map(int, input().split()))
    
    # 各部分集合について、その荷物の合計重量を計算
    subset_weight = [0] * (1 << N)
    for mask in range(1 << N):
        total = 0
        for i in range(N):
            if mask & (1 << i):
                total += W[i]
        subset_weight[mask] = total
    
    # 有効な部分集合（重量がC以下）を列挙
    valid_subsets = []
    for mask in range(1 << N):
        if subset_weight[mask] <= C:
            valid_subsets.append(mask)
    
    # dp[mask] = mask で表される荷物を全て運ぶのに必要な最小往復回数
    INF = float('inf')
    dp = [INF] * (1 << N)
    dp[0] = 0
    
    full_mask = (1 << N) - 1
    
    for mask in range(1 << N):
        if dp[mask] == INF:
            continue
        
        # 残りの荷物
        remaining = full_mask ^ mask
        
        # 残りの荷物の部分集合を列挙
        sub = remaining
        while sub > 0:
            if subset_weight[sub] <= C:
                new_mask = mask | sub
                if dp[new_mask] > dp[mask] + 1:
                    dp[new_mask] = dp[mask] + 1
            # 次の部分集合
            sub = (sub - 1) & remaining
    
    print(dp[full_mask])

solve()

---

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