と名付けました
何？
「最大の個数/長さを求めよ」というときに、「長さ i にするために必要な最小コストは？」というDPをやって二部判定問題にするよ！
DPの遷移分の計算量を O(N) から O(log N) に減らすよ！
例
・LIS (最長増加列)
長さ N の数列 a[i] があるとき、単調増加な部分列で最長のものの長さをもとめる！
-- 愚直な実装
a[i] を一番最後とする列で最長のものを dp[i] とする。
遷移は a[j] < a[i] な jすべてについての a[j]+1 の max (なければ1) とする。
遷移に最悪 O(N) かかるので、O(N^2) のアルゴリズムである。
-- 高速化
dp[i][k] を「 i 番目までで長さ k の部分列を作るときの、最後の要素の最小値」とする。作れない場合は INF とする。そうすると、最後 dp[N][k] の中で INF でないような k の最大値が答えとなる。
遷移はどうなるか考える。dp[i-1][k] までは更新されてるとして、a[i] を使う部分列について考えると、 dp[i-1][k] の中で a[i] 以下の場所は変化せず、a[i] より大きい最小の k の場所だけ値が a[i] に更新される (INFの場所もそう)。
結局 i の情報は持つ必要がないので dp[k] のリストを更新する形となり、また dp[k] は単調増加なので遷移は二部探索が使えて O(log N) でできる。
「列を作るなら、ラストをなるだけ小さくしたい」という思想が大事。調べたい情報より強いことを求めるのでオーバーキルDPと呼ぶことにしました。
