monotone や monge 周りの話
調べていたら頭がこんがらがってきたので纏めることとする。
monotone
$ N \times M行列$ Aが monotone であるとは、任意の$ 1 \le i < Nに対して$ \argmax_j A_{i,j} \le \argmax_j A_{i+1,j}が成り立つことを言う。
totally monotone
$ N \times M行列$ Aが totally monotone であるとは、$ Aの任意の部分行列が monotone であることを言い、これは$ Aの任意の$ 2 \times 2の部分行列が monotone であることと同値である。
上記は $ \argmin による定義も存在するので注意。また、同じ値が存在するときは適切な順序を決めて $ \argmax が一意に定まるものとする。
monge
$ N \times M行列$ Aが monge であるとは、任意の$ 1 \le i < j \le N,1 \le k < l \le Mに対して$ A_{i,k}+A_{j,l} \le A_{i,l}+A_{j,k}が成り立つことを言い、これは$ Aの任意の$ 2 \times 2の部分行列が monge であることと同値である。
また、$ Aが monge であるならば$ Aは totally monotone(ただし$ \argmin)である。$ A_{i,j},A_{i+1,j},A_{i,j+1},A_{i+1,j+1}が monge であることから示すことが出来る。
また、$ A_{i,k}+A_{j,l} \ge A_{i,l}+A_{j,k}が必ず成り立つ場合は anti-monge と言う。この場合も tottaly monotone となる。
monotone である行列$ Aに対して、それぞれの行の最小値を monotone minima を使うことによって$ \mathrm{O}(N + M\log N)で求めることが出来る。これはスライドアクセスで行うことが出来る。
これは、中央の行の最小値を愚直に全探索し、それより上の行と下の行について再帰して問題を解くアルゴリズムである。
totally monotone である行列$ Aに対して、それぞれの行の最小値を SMAWK Algorithm を使うことによって$ \mathrm{O}(N+M)で行うことが出来る。これはランダムアクセスを行う必要がある。
これは、$ N行のうち$ N/2個の行を飛び飛びに選び、それらのいずれかの行で最小値を取る高々$ N/2個の列を全て網羅する形で列を枝刈りし、再帰的に問題を解くアルゴリズムである。
Max Convolution
長さ$ Nの整数列$ Aと長さ$ Mの整数列$ Bに対して、$ C_i = \max_j \{A_j + B_{i-j}\}で定義される数列$ Cを求めることを考える。
もし、$ A,Bの両方が上に凸であれば$ A_i-A_{i-1},B_j-B_{j-1} の$ N+M個の要素からなる多重集合から貪欲に大きい方から$ k個取りそれらの総和を求めればよいため$ \mathrm{O}(N+M)で$ Cを求めることが出来る。
$ Bのみが上に凸である場合、$ X_{i,j}=A_j + B_{i-j}となる$ (N+M-1) \times Mの行列$ Xを考える。ただし、添え字の範囲がおかしい部分は$ Bの凸性を保つ十分小さい値を入れることとする。この$ Xは$ Bが上に凸であるため anti-monge である。よって、totally monotone である。
よって$ Xに対して SMAWK Algorithm を適用することによってこの場合も$ Cを$ \mathrm{O}(N+M)で求めることが出来るが、実装は前者の方が軽い。
$ Bが下に凸である場合、上記と同様に$ Xを定義する。このまま先程のように monge に持ち込みたいが添え字の範囲がおかしい部分に$ -\inftyを入れてしまうと monge 性が崩れてしまう。
$ Xの上の三角の部分に対して問題を解くことを考える。$ Xから長方形領域を切り出しその部分は monge 性があるため SMAWK Algorithm を使い、他の$ 2個の三角行列についても再帰をすることでこの部分は行最小値を$ \mathrm{O}(M\log M)で求めることが出来る。
よって、真ん中の長方形部分も SMAWK Algorithm を使い処理することによって $ C を$ \mathrm{O}(N + M\log M)で求めることが出来る。
$ Cを$ \minで定義する場合も$ A,Bに$ -1をかけることで上記のいずれかのケースに帰着させればよい。