概要

荷物 \(N(\le 15)\) 個を重さ制限つきのトラック \(M(\le 15)\) 台に「各荷物ちょうど1台」割り当てられるかを、ビットマスクDP（部分集合DP）で判定します。

考察

重要な気づき

• \(N,M\le 15\) なので、「どの荷物をすでに積んだか」をビットマスク（\(0\sim 2^N-1\)）で管理するDPが現実的です。
• 各トラックには「積む荷物の集合」を選ぶ必要があります。これは「残っている荷物集合の部分集合」を選ぶ問題になります。

素朴解が厳しい理由

トラックごとに「残りの部分集合を全列挙」すると、状態数が \(2^N\)、各状態で部分集合列挙が最大 \(2^{N}\) なので、最悪 \(O(M\cdot 3^N)\) 近くになりがちです（部分集合DPでよく出る形）。\(N=15\) でも実装次第で重くなります。

それをどう解決するか（高速化の工夫）

1. 事前に不可能を弾く
   • \(\max_i W_i > \max_j C_j\) なら、その荷物はどのトラックにも載らず即 No
   • \(\sum_i W_i > \sum_j C_j\) なら総容量不足で即 No
2. トラック台数を減らす
   • 実際に荷物が載るトラックは高々 \(N\) 台なので、\(M>N\) のときは大きい容量のトラックから \(N\) 台だけ残せば十分（小さいトラックは役に立ちにくい）。
3. 容量の小さいトラックから処理
   • 小さい容量のトラックは積める部分集合が限られるため、到達可能状態（reachable）が増えにくく、DPが膨らむのを抑えやすいです。
4. 部分集合の列挙方法を状況で切り替える
   • そのトラックに載せられる集合の一覧 fit_list（重さ和 \(\le cap\) の部分集合）を先に作り、それを使って遷移する方法
   • ある状態 mask の「残り集合 rem の全部分集合」をなめる方法
   • どちらが少ないかを見て、軽い方を選びます。

アルゴリズム

1. 前処理

• full = (1<<N)-1 を「全荷物を積み終えた状態」とする。
• トラック容量 \(C\) を大きい順に並べ、\(M=\min(M,N)\) 台だけ残す（大きいものを優先）。
• さらにDPは小さい容量から回したいので、残した \(C\) を昇順に並べ替える。
• 各部分集合 mask について重さ和 sum_w[mask] を前計算する。
  • 例：mask の最下位ビット lsb を取り、sum_w[mask] = sum_w[mask ^ lsb] + W[i] の形で \(O(2^N)\) で作れる。

2. DP定義

• dp[mask] = True
  「これまで処理したトラックを使って、荷物集合 mask（ビット1の荷物）を積み終えることが可能」
• 初期：dp[0]=True（まだ何も積んでいない）
• reachable に「現在 True の mask のリスト」を持ち、無駄な全走査を減らす。

3. 遷移（各トラック容量 cap について）

• まず、各 mask in reachable について rem = full ^ mask（残り荷物）を計算し、
  • もし sum_w[rem] <= cap なら「残り全部をこのトラックに載せて終了」できるので即 Yes。
• 次に、そのトラックに載せられる部分集合 sub（sum_w[sub] <= cap）を使って遷移する。
  • 「このトラックを空で使う」も許されるので new_dp = dp[:] から開始する。
  • 遷移先は nm = mask | sub（sub が mask と重ならないことが条件）。

部分集合列挙は2通りを比較して少ない方を使います： - fit_list を全状態で共有して回す：sub in fit_list を見て (sub & mask)==0 を満たすなら遷移 - 状態ごとに rem の部分集合を回す：sub = rem; sub=(sub-1)&rem で列挙し sum_w[sub] <= cap なら遷移

最後に dp = new_dp、reachable も更新し、全トラック処理後に dp[full] なら Yes、そうでなければ No。

（簡単な例） - \(N=3\) なら状態は mask=0..7。 - 例えば mask=101(2) は「荷物1と3を積み終えた」、残りは rem=010。 - 次のトラック容量が十分なら rem を全部載せて full=111 に到達できます。

計算量

• 時間計算量: 典型的には \(O(2^N + \sum_{j=1}^{M} (\text{reachable数}) \times \min(|\text{fit\_list}_j|, 2^{\text{残り個数}}))\)
  （最悪形を雑に書くと \(O(M\cdot 3^N)\) 方向ですが、\(N\le 15\)・到達状態管理・列挙切替・小容量から処理で実用上十分速くしています）
• 空間計算量: \(O(2^N)\)（dp, sum_w, popc など）

実装のポイント

• \(M>N\) のときは大きい容量を \(N\) 台だけ残す：非空トラックは高々 \(N\) 台なので、余分な小容量トラックは捨てても可否に影響しません。

• sum_w[mask] を前計算して、部分集合の重さ判定を \(O(1)\) にするのが重要です。

• 小さい容量から処理すると到達状態が膨らみにくく、DPが安定します。

• 列挙方法の切替（fit_list vs rem の部分集合列挙）が高速化の肝で、容量が小さいとき・残りが少ないときの両方に対応できます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    W = list(map(int, input().split()))
    C = list(map(int, input().split()))

    full = (1 << N) - 1

    C.sort(reverse=True)
    M = min(M, N)
    C = C[:M]
    if not C:
        print("No")
        return

    if max(W) > max(C):
        print("No")
        return
    if sum(W) > sum(C):
        print("No")
        return

    # Process smaller capacities first to keep reachable states small
    C.sort()

    sum_w = [0] * (1 << N)
    for mask in range(1, 1 << N):
        lsb = mask & -mask
        i = lsb.bit_length() - 1
        sum_w[mask] = sum_w[mask ^ lsb] + W[i]

    popc = [0] * (1 << N)
    for mask in range(1, 1 << N):
        popc[mask] = popc[mask >> 1] + (mask & 1)

    dp = [False] * (1 << N)
    dp[0] = True
    reachable = [0]

    for cap in C:
        # If any current state can finish all remaining items with this truck, done
        for mask in reachable:
            rem = full ^ mask
            if sum_w[rem] <= cap:
                print("Yes")
                return

        fit_list = [sub for sub in range(1, 1 << N) if sum_w[sub] <= cap]
        fit_len = len(fit_list)

        new_dp = dp[:]  # allow leaving this truck empty
        new_reachable = reachable[:]  # start with existing states

        for mask in reachable:
            if mask == full:
                continue

            rem = full ^ mask
            # Choose faster enumeration strategy per state
            if fit_len < (1 << (N - popc[mask])):
                for sub in fit_list:
                    if (sub & mask) == 0:
                        nm = mask | sub
                        if not new_dp[nm]:
                            new_dp[nm] = True
                            new_reachable.append(nm)
            else:
                sub = rem
                while sub:
                    if sum_w[sub] <= cap:
                        nm = mask | sub
                        if not new_dp[nm]:
                            new_dp[nm] = True
                            new_reachable.append(nm)
                    sub = (sub - 1) & rem

        dp = new_dp
        reachable = new_reachable

    print("Yes" if dp[full] else "No")


if __name__ == "__main__":
    main()

---

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