Monotone MinimaとOnline-Offline変換に感動した話
※特に新奇性のある話ではないです
Monotone MinimaとOnline-Offline変換を学んですげ〜となったので簡単なメモを残しておきます
・Monotone Minima(以下MMと書きます)
これはMonotoneである二変数関数f(i,j)について、それぞれのiに対してf(i,j)が最小となるようなjを高速に求めてくれるアルゴリズムです 原理自体はとても簡単で、Monotoneという制約から、分割統治的に問題を解いていけるというだけです 一方で、このアルゴリズムで得られる配列をXとした時、f(i,j)がXに依存しているとそのまま計算することはできません(つまりOfflineにしか対応していない)
・(DPが)Onlineとは？
DP配列を計算する時に、dp[i]の値がdp[j](j<i)に依存するみたいなDPがよくあります(Frog 1とかもそう) こういうDPでは、dp[i]の値を求めるためにdp[i-1]を求める必要があって、さらにdp[i-1]を求めるためにはdp[i-2]が必要で……となってdp表を埋めていく順序が決まっています これがOnlineDPと呼ばれています 一方で、OfflineDPはdp[i]の値がdp[j]の値によらないので、好きなところから計算を始めることができます 当然Onlineの方が制限が厳しく、Offlineの方が計算しやすいです
・Online-Offline変換とは？
単純に言ってしまえば、MMのようなOfflineの場合限定で高速化できるアルゴリズムをOnlineDPに適応するためにOnlineDPをOfflineDPに変換することです この変換をするためには、複数の遷移について、それぞれの遷移が独立していて分解できることが必要です 例えば、dp[i]=min(dp[j]), j<i みたいな時は成り立っていて、dp[i]をそれぞれのjに対してdp[i]=min(dp[i],dp[j])と更新することを繰り返して得られるからです まあdp[i]をiとjの二項演算の積みたいにかければ大体大丈夫な気がします(ここ怪しい)
・具体的なアルゴリズム
実は分割統治法とだいたい同じです solve(l,r)を区間[l,r)についてdp[l]~dp[r-1]を求める関数としておきます solve(0,N)が呼べればそれが答えになっています もう一個、induce(l,m,r)という関数を作ります これは、区間[l,m)から区間[m,r)を跨ぐような遷移をまとめて計算します dp[l]~dp[m-1]の値をinduceを呼ぶ前に埋めておければ、induceによってdp[m]~dp[r-1]それぞれに対して、[l,m)の遷移を反映させられます ということでsolve(l,r)は、m=(l+r)/2として、solve(l,m)→induce(l,m,r)→solve(m,r)の順で計算することに相当しています
・もう少し詳しく
solve(0,8)を考えます m=4なので、solve(0,4)を呼ぶことでdp[0],dp[1],dp[2],dp[3]の値が手に入ります induce(0,4,8)を考えると、dp[0]~dp[3]からdp[4]~dp[7]の遷移をすることになります ここで全ての0<=i<4,4<=j<8の(i,j)についてdp[i]->dp[j]の遷移をやっているとO(N^2)になってしまうのでいい感じに高速化する必要があることに注意 あとはsolve(4,8)を呼べばいいです induce(0,4,8)をした時点ではdp[5]はdp[0]~dp[3]からの遷移しか受けていないんですが、solve(4,8)を呼ぶとsolve(4,6)が呼ばれて、ここのinduce(4,5,6)でdp[4]->dp[5]の遷移が入って大丈夫になります 全体で見るとちゃんとdpが昇順に計算されていることがわかります
・結局MMはどうやって使うの？
induceの高速化に使えます 例えばdp[i]=min(dp[j]+(i-j)^2) (j<i) みたいな更新ならf(i,j)=dp[j]+(i-j)^2がMonotoneになっていて、ここにMMが使えて高速化できます f(i,j)の中にdp[j]が入っていて不可能な気持ちになりますが、今回の遷移元はj∈[l,m)に限られていて、さらにinduce(l,m,r)の時、先にsolve(l,m)をしているのですでにdp[l]~dp[m-1]が求まっています そのため、f(i,j)の中のdp[j]は定数として扱えます できました
・実用性はありますか？ 使い所はどうやって見極めますか？
まず、Online-Offline変換をする時点でlogNが余計につきます このため、induceがそれなりに早くないと使えません 基本的には愚直なinduceがN^2なので、これをo(N^2)にできないと使えなさそうです induceにMMを利用するとN^2がNlogNになってこれは実用性があります(全体O(NlogNlogN)) あとはこちら*1の具体例が参考になりました induceとしてmin(abs(dp[l,m)-X))が計算できればいいんですけど、dp[l,m)をまとめてソートしておくことで[m,r)の更新が一箇所あたりlogNになってinduceがNlogNになっています この問題の場合はさらに高速化できてinduceがO(N)になるようです
・今後の課題
Offlineで高速になるようなinduceにどんなものがあるか気になりますね もし見つけた/知ってるなら教えてもらえるとうれしくなります
・ねむすぎ 今日学んだばっかりなので嘘が多そう 気が向いたら追記します 特に練習問題とか追加したいっす
