半分全列挙
例1
4つの長さN=4000の数列がある。要素を一つずつ選んで和が0になる組み合わせを数えたい。
素朴に全探索すると4000^4で間に合わない。
前処理: 二つの数列について4000^2ですべての組み合わせの和を列挙する。これをXとする。
残り二つの数列について4000^2で全探索する。二つの値の和をsとする。
Xから-sを探す。
Xをソートして二分探索: 全体でO(N^2logN) 和の値域が狭い時、頻度表で定数オーダーにすることができてO(N^2) 例2
問題
サイズN=40の集合からいくつか選ぶ
集合の要素は重さwi, 価値viの品物である
選ばれた品物の重さがWを超えてはいけない
価値の総和を最大化せよ
wやvは10^15までの値を取りうる
ナップサック問題。値の範囲が大きいのでDPで解くことができない。 2^40は大きすぎて全探索できない。2^20なら全列挙できる。これをXとする。
残りの半分について2^20で全探索する。重さの和をwとするなら、Xから重さがW-wを超えない最大のvを見つける問題になる。
全体として2^(N/2)N
なお値の範囲が小さいときには「重さ→価値」のテーブルを使うDPでO(NW)