例1
- 4つの長さN=4000の数列がある。要素を一つずつ選んで和が0になる組み合わせを数えたい。
- 素朴に全探索すると4000^4で間に合わない。
- 前処理: 二つの数列について4000^2ですべての組み合わせの和を列挙する。これをXとする。
- 残り二つの数列について4000^2で全探索する。二つの値の和をsとする。
- Xから-sを探す。
例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)