概要

本問題は、与えられた \(N\) 個の荷物を、最大積載量 \(M\) のトラックにすべて積み込むために必要なトラックの最小台数を求める問題です。荷物の個数 \(N\) が最大でも \(20\) と非常に小さいことが特徴であり、ビットDP（動的計画法）を用いることで効率的に解くことができます。

考察

貪欲法では解けない理由

「重い荷物から順にトラックに詰める」といった単純な貪欲法は、一見正しそうに見えますが、最適解を導けないケースが存在します。 例えば、\(M = 10\), 荷物の重さが \([5, 4, 4, 3, 2, 2]\) の場合を考えます。 * 貪欲法（降順に詰める）: * トラック1: \(5 + 4 = 9\) (残り \(1\)、これ以上積めない) * トラック2: \(4 + 3 + 2 = 9\) (残り \(1\)、これ以上積めない) * トラック3: \(2\) * ⇒ 合計 \(3\) 台必要になります。 * 最適解: * トラック1: \(5 + 3 + 2 = 10\) * トラック2: \(4 + 4 + 2 = 10\) * ⇒ 合計 \(2\) 台で運ぶことができます。

このように、荷物の組み合わせを網羅的に探索する必要があります。これは「ビンパッキング問題」と呼ばれるNP困難な問題ですが、今回は \(N \le 20\) と非常に小さいため、すべての積み方の状態を探索するアプローチが可能です。

制約に着目する

荷物の個数 \(N\) が \(1 \le N \le 20\) と非常に小さいことに注目します。 「どの荷物をすでにトラックに積んだか」という状態は、各荷物について「積んだ / まだ積んでいない」の \(2\) 通りがあるため、全体で \(2^N\) 通り（\(N=20\) のとき \(2^{20} \approx 1.05 \times 10^6\) 通り）しかありません。 したがって、すでに積んだ荷物の集合をビット列で表すビットDPが適用できます。

アルゴリズム

すでにトラックに積んだ荷物の集合を、整数 \(S\)（\(0 \le S < 2^N\)）のビット表現で管理します。\(S\) の \(i\) 番目のビットが 1 であれば \(i\) 番目の荷物は積載済み、0 であれば未積載であることを表します。

各状態 \(S\) において、トラックを最も効率よく使う（＝トラックの台数を最小にし、さらに最後に使っているトラックの空き容量を最大にする）ことを考えます。 そこで、DPテーブル dp[S] に以下の2つの情報をペアとして保持します： 1. cnt: すでに満杯（またはこれ以上積めない）になって送り出したトラックの数 2. used: 現在使用中の最後のトラックに積まれている荷物の重さの合計

最適な状態は、「cnt が最小で、かつ cnt が同じなら used が最小」となるものです。

遷移

状態 \(S\) から、まだ積んでいない荷物 \(i\)（\(S\) の \(i\) 番目のビットが 0）を新しく積むことを考えます。 現在の状態の値を \((cnt, used)\) としたとき、遷移は以下の2パターンになります：

1. 同じトラックにまだ積める場合 (\(used + W_i \le M\)): 新しい状態の値は \((cnt, used + W_i)\) に更新されます。
2. 新しいトラックが必要な場合 (\(used + W_i > M\)): 現在のトラックを送り出し、新しいトラックに荷物 \(i\) を積みます。 新しい状態の値は \((cnt + 1, W_i)\) に更新されます。

すべての状態 \(S\) について、まだ使っていないすべての荷物 \(i\) を遷移させて dp テーブルを更新していきます。 最終的な答えは、すべての荷物を積み終えた状態 \(dp[2^N - 1]\) における cnt + 1（送り出したトラック数 + 現在使っているトラック1台）となります。

計算量

• 時間計算量: \(O(N \cdot 2^N)\) 状態数が \(2^N\) 個あり、各状態からの遷移（次の荷物の選択）が \(N\) 通りあります。\(N = 20\) のとき、全体の遷移回数は \(20 \times 2^{20} \approx 2.1 \times 10^7\) 回となり、実行時間制限に十分間に合います。
• 空間計算量: \(O(2^N)\) DPテーブルのサイズは \(2^N\) です。\(2^{20}\) 個の要素を持つ配列は、メモリ制限に対しても十分に余裕があります。

実装のポイント

Pythonなどのインタプリタ言語では、DPの要素としてタプル (cnt, used) を直接持つと、オブジェクトの生成や比較のオーバーヘッドにより実行時間が厳しくなり、TLE（実行時間制限超過）になる可能性があります。

そこで、提供されたコードではビット演算を利用して2つの情報を1つの整数に圧縮しています。

• 最大積載量 \(M \le 10^9 < 2^{30}\) であるため、下位30ビットを used に、それより上のビットを cnt に割り当てます。 $\(\text{val} = (\text{cnt} \ll 30) \mid \text{used}\)$

• このように圧縮することで、値の大小比較 n_val < dp[next_S] が、そのまま「cnt の最小化、同値なら used の最小化」という優先度付きの比較と一致します。これにより、タプルやオブジェクトを生成するオーバーヘッドを排除し、高速な動作を実現しています。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    M = int(data[1])
    W = [int(x) for x in data[2:]]
    
    # dp[S] = (cnt << 30) | used
    # cnt: すでに満杯になって送り出したトラックの数
    # used: 現在使用中のトラックの積載量
    LIMIT = 1 << N
    INF = 0x3fffffffffffffff
    dp = [INF] * LIMIT
    dp[0] = 0
    
    MASK = (1 << 30) - 1
    p2_W = [(1 << i, W[i]) for i in range(N)]
    
    for S in range(LIMIT):
        val = dp[S]
        cnt = val >> 30
        used = val & MASK
        for p2, w in p2_W:
            if not (S & p2):
                n_used = used + w
                if n_used <= M:
                    n_val = (cnt << 30) | n_used
                else:
                    n_val = ((cnt + 1) << 30) | w
                next_S = S | p2
                if n_val < dp[next_S]:
                    dp[next_S] = n_val
                    
    ans = (dp[LIMIT - 1] >> 30) + 1
    print(ans)

if __name__ == '__main__':
    solve()

---

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