半分全列挙
例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を見つける問題になる。
- なお値の範囲が小さいときには「重さ→価値」のテーブルを使うDPでO(NW)
https://algo-logic.info/split-and-list/
https://www.hamayanhamayan.com/entry/2018/01/06/112704