概要

\(N\) 個の荷物を \(M\) 台のトラック（それぞれ容量制限あり）にすべて積み込めるかどうかを判定する問題です。荷物の数とトラックの数がともに最大 15 と小さいため、ビットDP（Bitmask DP）を用いて効率的に解くことができます。

考察

1. 単純な探索の難しさ

各荷物をどのトラックに積むかを愚直に試すと、最大で \(M^N = 15^{15}\) 通りの組み合わせがあり、制限時間内に計算が終わりません。また、荷物を積む順番によっても結果が変わる可能性があるため、工夫が必要です。

2. 制約に注目

荷物の数 \(N\) が 15 と非常に小さいことに注目します。このように「ある要素を使ったか使っていないか」という状態が少ない場合、ビットDPが有効です。

荷物の集合を \(2^N\) 通りの整数（ビットマスク）で表すことで、「どの荷物を積み終えたか」という状態を管理できます。

3. 最適な状態の定義

ある荷物の集合 mask を積み込むとき、できるだけ「余裕」を持たせておいたほうが、残りの荷物を積み込める可能性が高まります。具体的には、以下の優先順位で状態を更新します。 1. 使用するトラックの台数を最小にする 2. 台数が同じなら、最後に使っているトラックの残り容量を最大にする

トラックを容量の大きい順にソートしておくことで、より効率的に荷物を詰め込むことができます。

アルゴリズム

ビットDPによる解法

以下の2つの配列を用意します。

• dp_k[mask]: 荷物の集合 mask を積み込むのに必要な最小のトラック台数（のインデックス）
• dp_rem[mask]: そのときの最後のトラックの最大残り容量

手順

1. 前処理:
   • トラックの容量 \(C\) を降順（大きい順）にソートします。
   • 全体の荷物の重さの合計が全トラックの容量合計を超えている場合は、即座に No と出力します。
2. 初期化:
   • dp_k[0] = 0（荷物なしなら 0 番目のトラックを使用）
   • dp_rem[0] = C[0]（残り容量は 0 番目のトラックの全容量）
   • それ以外を到達不可能な値で初期化します。
3. 遷移: 各 mask について、まだ積んでいない荷物 \(i\) を追加することを考えます。
   • 現在のトラックに積める場合: そのまま積み、残り容量を減らします。
   • 次のトラックに積む場合: 次のトラックの容量 \(C[k+1]\) が荷物 \(i\) 以上であれば、新しいトラックを使用して積みます。
4. 判定: すべての荷物を積み込んだ状態 (1 << N) - 1 において、使用したトラックの数が \(M\) 台以内であれば Yes、そうでなければ No です。

計算量

• 時間計算量: \(O(N \cdot 2^N)\)
  • 状態数が \(2^N\) で、各状態からの遷移（荷物の選択）が \(N\) 通りです。\(N=15\) のとき \(15 \times 2^{15} \approx 4.9 \times 10^5\) となり、制限時間内に十分間に合います。
• 空間計算量: \(O(2^N)\)
  • ビットマスクの状態を保持する配列のサイズです。

実装のポイント

• トラックのソート: 容量の大きいトラックから使うことで、積める確率を上げるとともに、DPの遷移をシンプルにできます。

• 早期判定: sum(W) > sum(C) のチェックを入れることで、明らかに不可能なケースを排除できます。

• ビット演算: mask & (1 << i) で荷物 \(i\) が使用済みか判定し、mask | (1 << i) で使用済みに更新します。コード内では pow2 配列を事前計算して高速化を図っています。

  ソースコード

import sys

def solve():
    # 全ての入力を読み込み、空白で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N（荷物の数）とM（トラックの数）を取得します
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各荷物の重さと各トラックの積載制限を取得します
    W = list(map(int, input_data[2:2+N]))
    C = list(map(int, input_data[2+N:2+N+M]))
    
    # 荷物の重さの合計がトラックの積載制限の合計を超えている場合は不可能です
    if sum(W) > sum(C):
        print("No")
        return

    # トラックの積載制限を降順にソートします
    # 容量の大きいトラックから優先的に使うことで、すべての荷物を積み込める可能性を最大化します
    C.sort(reverse=True)
    
    # トラックの数が荷物の数より多い場合、最大でもN台のトラックしか必要ありません
    if M > N:
        C = C[:N]
        M = N
        
    # ビットDPを用いて、荷物の各集合（mask）を積み込むのに必要な最小のトラック数と、
    # その際に最後に使ったトラックの残り容量を管理します。
    # dp_k[mask]: maskで表される荷物の集合を積み込むのに必要な最小のトラックのインデックス (0からM-1)
    # dp_rem[mask]: その時の最後のトラックの最大残り容量
    dp_k = [M + 1] * (1 << N)
    dp_rem = [-1] * (1 << N)
    
    # 初期状態：荷物を一つも積んでいないとき、0番目のトラックを使用し、その残り容量はC[0]です
    dp_k[0] = 0
    dp_rem[0] = C[0]
    
    # ビット演算のための2の累乗を事前に計算しておきます
    pow2 = [1 << i for i in range(N)]
    
    # 全ての荷物の集合（ビットマスク）についてループします
    for mask in range(1 << N):
        k = dp_k[mask]
        rem = dp_rem[mask]
        
        # この状態が到達不可能な場合はスキップします
        if k >= M:
            continue
        
        # まだ積み込んでいない荷物 i を追加することを試みます
        for i in range(N):
            if not (mask & pow2[i]):
                new_mask = mask | pow2[i]
                wi = W[i]
                
                # 選択肢1: 現在のトラック k に荷物 i を積む
                if wi <= rem:
                    nk, nrem = k, rem - wi
                # 選択肢2: 次のトラック k+1 に荷物 i を積む
                elif k + 1 < M and wi <= C[k+1]:
                    nk, nrem = k + 1, C[k+1] - wi
                else:
                    # どちらのトラックにも積めない場合はスキップ
                    continue
                
                # dp[new_mask] を更新します（使用トラック数が少ない、またはトラック数が同じなら残り容量が多い方を優先）
                if nk < dp_k[new_mask]:
                    dp_k[new_mask] = nk
                    dp_rem[new_mask] = nrem
                elif nk == dp_k[new_mask] and nrem > dp_rem[new_mask]:
                    dp_rem[new_mask] = nrem
                        
    # すべての荷物を積み込んだ状態（(1 << N) - 1）が有効なトラック数で到達可能か判定します
    if dp_k[(1 << N) - 1] < M:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    solve()

---

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