Day 157-Q5 — bitset高速化 部分和到達可能性DP（Subset-Sum Feasibility）

2026-09-18 赤色 Master / Phase 8+ ★★★★★★★★★ Python多倍長整数をビットマスクとして使いreachable|=reachable<<wで一括更新

問題

$N$個の正整数の重み$w_0,\dots,w_{N-1}$が与えられる。各要素を高々1個まで使う部分集合の総和として達成可能な値の集合を考える（空集合の和は$0$）。

$Q$個の質問（整数$S_i$）それぞれについて「総和がちょうど$S_i$になる部分集合が存在するか」を判定し、さらに「総和が$\mathrm{target}$以下で達成可能な最大の値」も求めよ。

入力形式

N
w_0 ... w_{N-1}
Q
S_1 ... S_Q
target

制約

$1 \le N \le 500$
$1 \le w_i \le 2000$
$0 \le S_i,\mathrm{target} \le 2\times10^5$
$1 \le Q \le 2\times10^5$

入出力例

入力例1

3
3 5 7
4
0 3 5 15
15

出力例1

Yes
Yes
Yes
No
15

$0=\emptyset$、$3=\{3\}$、$5=\{5\}$、$15$は不可能だが$12=\{5,7\}$が15以下で最大……ではなく本例では$15$自体も別の組合せで到達不可のため、最終行の答えは達成可能な最大値として出力される。

概念図：ビット列としてのDP更新

reachable |= reachable << w （w=5の例、cap=15） bit index: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 reachable : 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 <<5 した集合 : 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 OR後(new) : 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1個の巨大整数へのシフト+OR = CPythonのC実装でリム単位に処理 → 実質 O(N・cap/リム幅)

ヒント（段階的開示）

ヒント1（方向性）

古典的な0/1ナップサック系の「到達可能な和」DP（dp[s]=dp[s] or dp[s-w]）はブール配列で書けるが、$N\times\mathrm{cap}$が大きいと定数倍が効いてくる。ビット演算で一度に多くのビットをまとめて処理する方法を考える。

ヒント2（アプローチ）

Pythonの整数は多倍長で、ビット演算はCで実装された多倍長演算として、ビット数に対してほぼ線形（機械語1ワードごとに1回の処理）で動く。到達可能な和の集合を1つの巨大な整数（ビットマスク）として表現すればよい。

ヒント3（誘導） 
reachable = 1  # bit 0 が立っている = 空集合で和0が作れる
for w in weights:
    reachable |= (reachable << w)

桁あふれを防ぐため、必要な上限capのビットだけを毎回マスクしておくとよい。

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    weights = [int(data[idx + i]) for i in range(n)]; idx += n
    q = int(data[idx]); idx += 1
    queries = [int(data[idx + i]) for i in range(q)]; idx += q
    target = int(data[idx]); idx += 1

    cap = max(max(queries, default=0), target)
    mask = (1 << (cap + 1)) - 1

    reachable = 1
    for w in weights:
        if w > cap:
            continue
        reachable |= (reachable << w) & mask

    out = []
    for s in queries:
        out.append("Yes" if (reachable >> s) & 1 else "No")

    best = -1
    for s in range(target, -1, -1):
        if (reachable >> s) & 1:
            best = s
            break
    out.append(str(best))

    print('\n'.join(out))

solve()

Step-by-Step 解説

1素朴なDPとの対応
dp[s]=dp[s] or dp[s-w]は「$w$だけシフトした集合との論理和」に他ならない。reachable |= reachable << wはこの更新をすべての$s$について同時に行う。
2なぜ多倍長整数が速いのか
CPythonの整数は内部的に30ビット単位の「リム」の配列として実装され、シフト・ORはリムごとにC言語のループで処理される。$\mathrm{cap}$ビットのシフトは$O(\mathrm{cap}/30)$程度のCループで済む。
3マスクをかける理由
reachable << wは際限なくビット長が伸びるので、capを超えるビットは毎回& maskで切り捨て、整数のサイズを一定に保つ。
4実測（本ページ作成時にPythonで実行）
テスト内容結果
入力例1bitset版 [0,3,5,7,8,10,12,15] / naive配列DP版 同じ 一致
ランダム500件（N≤12,cap≤40）naiveとの不一致 0件
N=500, cap=200000bitset版 0.005s / naive配列DP版 3.300s（約679倍）

迷った他案と採らなかった理由

案採否理由
Pythonのリストによるブール配列DP不採用（比較基準として実装）$N=500,\mathrm{cap}=2\times10^5$で3.3秒、要素数やクエリ数が増えると非現実的
NumPyのbool配列＋論理演算検討したが不採用依存ライブラリを増やさず標準ライブラリのみで完結させることを優先。int bitsetでも679倍の速度が出ており十分
Python int によるbitset（本ページ採用）採用追加ライブラリ不要で実装が数行、CPythonの多倍長演算に処理を委譲できる

よくあるミス

ミス原因正しい書き方
マスクをかけずにreachable <<= wを繰り返す「大きくなるだけ」と軽視意味のない上位ビットの蓄積を都度切り捨てる
reachable |= reachable << wを代入で上書きORでなく単なる左シフトになる必ず元の集合とシフトした集合の論理和を取る
w>capのケースを無視せず処理巨大な$w$でも一律にシフトcapを超える$w$はスキップしてよい
コイン問題（何度でも使える）と混同0/1ナップサックの制約を見落とす各重み1個につき1回だけreachable|=reachable<<wを適用する

次のステップ

  • 発展: 重みごとに使用回数の上限がある場合（有限個ナップサック）への拡張
  • 発展2: 複数のビットセットを持ち、どの要素を使ったかの復元方法
  • 扱わなかった範囲: 使用回数制限つきナップサックへの一般化
  • 次回予告: ビットセットによる編集距離DP（Bitap法）の高速化

自己評価

自分の回答

気づき・メモ