[Monge まとめ①] Monge 性とは？

まえがき

LARSCH の読んだので解説記事を書こうと思ったが、説明が難しくてなかなか書けない…
Monge を理解していきたいので Monge の記事を書きます。
完全に理解しているわけではないのでご了承ください。

Monge の読み方

もんげ〜 と読みます。嘘です。

Monge の定義

実数からなる

$N\times M$ 行列について考えます。

$N\times M$ 行列

$A$ が Monge であるとは、以下の条件が成り立つことをいう。

• $1\le i_1<i_2\le N$ および
  $1\le j_1<j_2\le M$ を満たすすべての整数の組
  $(i_1,i_2,j_1,j_2)$ について、
  $A_{i_1,j_1}+A_{i_2,j_2}\le A_{i_1,j_2}+A_{i_2,j_1}$ である。

ABC224-B Mongeness

上三角 / 下三角 バージョンもよくでてきますね。

上三角バージョン

$N\times N$ 行列

$A$ は 上三角 (

$i>j$ ならば無効値) であるものとする。このとき、上の条件は以下のように言い換えられる。

• $1\le i_1<i_2\le j_1<j_2\le N$ を満たすすべての整数の組
  $(i_1,i_2,j_1,j_2)$ について、
  $A_{i_1,j_1}+A_{i_2,j_2}\le A_{i_1,j_2}+A_{i_2,j_1}$ である。

これは、無効値の部分を Monge になるように適当な値で埋め、さらに十分大きな定数

$\mathit{\text{INF}}$ を用いて、無効値だった部分

$(i>j)$ の各要素に

$\mathit{\text{INF}}\times (i-j)$ を加算すれば、通常の Monge として解釈できます。

つまり、右上や左下の一部分を無効値にしても Monge 性には問題がないということです。

(右下や左上だとうまくいかないことに注意しましょう。)

何につかえるの？

• $N\times M$ 行列
  $A$ が Monge であるとき、各行の最小値を
  $O(N+M)$ で求められます。
• $N$ 頂点のグラフがあり、頂点
  $i$ から頂点
  $j$ へ
  $(i<j)$ に移動するコストが
  $A_{i,j}$ であるとします。
  $A$ が Monge であるとき、単一始点最短路が
  $O(N)$ で求められます。
  • 辺をちょうど
    $d$ 回通る場合の
    $s-t$ 最短路が
    $O(N\log A_{max})$ で求められます。
• $A$ が Monge かつ単調 (区間が長いほど大きい) であるとき、区間 DP
  $\text{dp}[i][j]={\displaystyle \underset{i<k<j}{min}\{\text{dp}[i][k]+\text{dp}[k][j]\}+A_{i,j}}$ が
  $O(N^2)$ で計算できます。
• ほかいろいろ

Monge のおきもち

私なりの理解です。

ちょっと式変形してみましょう。

$$\begin{array}{rl}{A}_{i_1,j_1}+A_{i_2,j_2}& \le A_{i_1,j_2}+A_{i_2,j_1}\\ A_{i_2,j_2}-A_{i_2,j_1}& \le A_{i_1,j_2}-A_{i_1,j_1}\end{array}$$

ここで、

$A_{i_2,j_2}-A_{i_2,j_1}$ とは、「区間

$[i_2,j_1]$ の左端を固定し、右端を

$j_1\to j_2$ と広げたときのコストの増分」と解釈できます。

$A_{i_1,j_2}-A_{i_1,j_1}$ も同様に、「区間

$[i_1,j_1]$ の左端を固定し、右端を

$j_1\to j_2$ と広げたときのコストの増分」と解釈できます。

したがってこの式は、「右端を

$j_1\to j_2$ と広げたときのコストの増分」は、元々の区間

$[i,j_1]$ が長いほど大きい ことを表しています。

つまり、こうです。

$$A_{i,j_2}-A_{i,j_1}\le A_{i-1,j_2}-A_{i-1,j_1}\le A_{i-2,j_2}-A_{i-2,j_1}\le A_{i-3,j_2}-A_{i-3,j_1}\le \cdots$$

---

左端を広げる場合も同様です。

$$\begin{array}{rl}{A}_{i_1,j_1}+A_{i_2,j_2}& \le A_{i_1,j_2}+A_{i_2,j_1}\\ A_{i_1,j_1}-A_{i_2,j_1}& \le A_{i_1,j_2}-A_{i_2,j_2}\end{array}$$

とすれば、「左端を

$i_2\to i_1$ と広げたときのコストの増分」は、元々の区間

$[i_2,j]$ が長いほど大きい ことも表しています。

つまり、こうです。

$$A_{i_1,j}-A_{i_2,j}\le A_{i_1,j+1}-A_{i_2,j+1}\le A_{i_1,j+2}-A_{i_2,j+2}\le A_{i_1,j+3}-A_{i_2,j+3}$$

同値な条件

これをふまえると、以下の同値な条件がわかります。

$N\times M$ 行列

$A$ が Monge であるとは、以下の条件が成り立つことをいう。

• $1\le i<i+1\le N$ および
  $1\le j<j+1\le M$ を満たすすべての整数の組
  $(i,j)$ について、
  $A_{i,j}+A_{i+1,j+1}\le A_{i+1,j}+A_{i,j+1}$ である。

証明

$A_{i_1,j_1}+A_{i_2,j_2}\le A_{i_1,j_2}+A_{i_2,j_1}$ の方を (A) 、

$A_{i,j}+A_{i+1,j+1}\le A_{i+1,j}+A_{i,j+1}$ の方を (B) とします。
(A)

$⟹$(B) は明らかなので、(B)

$⟹$(A) を示せばよいです。

(B) を

$A_{i+1,j+1}-A_{i,j+1}\le A_{i+1,j}-A_{i,j}$ と変形すると、

$$A_{i+1,j_2}-A_{i,j_2}\le A_{i+1,j_2-1}-A_{i,j_2-1}\le \cdots \le A_{i+1,j_1+1}-A_{i,j_1+1}\le A_{i+1,j_1}-A_{i,j_1}$$

より

$A_{i+1,j_2}+A_{i,j_1}\le A_{i+1,j_1}+A_{i,j_2}$ です。
また、これを

$A_{i+1,j_2}-A_{i+1,j_1}\le A_{i,j_2}-A_{i,j_1}$ と変形すると、

$$A_{i_2,j_2}-A_{i_2,j_1}\le A_{i_2-1,j_2}-A_{i_2-1,j_1}\le \cdots \le A_{i_1+1,j_2}-A_{i_1+1,j_1}\le A_{i_1,j_2}-A_{i_1,j_1}$$

より

$A_{i_1,j_1}+A_{i_2,j_2}\le A_{i_1,j_2}+A_{i_2,j_1}$ が示せました。

Monge 行列の性質

転置しても Monge

定義の

$i,j$ が対称な形なので、

$i,j$ を入れ替えれば転置しても Monge であることがわかります。

部分行列も Monge

Monge 行列

$A$ から、任意に行を

$0$ 本以上削除し、任意に列を

$0$ 本以上削除した行列

$A^{\prime }$ を考えると、これも Monge です。

定義が、

$A$ から任意の

$2$ 行

$2$ 列を取り出すと

$A_{i_1,j_1}+A_{i_2,j_2}\le A_{i_1,j_2}+A_{i_2,j_1}$ である という形なので、

$A^{\prime }$ から取り出しても成り立ちます。

Monge ならば totally monotone

まずは monotone から定義していきましょう。

monotone

行ベクトル

$v$ に対して、

$\mathrm{argmin}(v)$ を

$min(v)=v_j$ なる

$j$ と定義する。ただし、同じ値が複数ある場合は適切に tie-break し、同じ値が存在しないようにする。これにより

$min(v)=v_j$ なる

$j$ は一意に定まる。

$N\times M$ 行列

$A$ が monotone であるとは、以下の条件が成り立つことをいう。

• $\mathrm{argmin}(A_1)\le \mathrm{argmin}(A_2)\le \cdots \le \mathrm{argmin}(A_N)$

totally monotone

$N\times M$ 行列

$A$ が totally monotone であるとは、以下の条件が成り立つことをいう。

• $A$ の任意の部分行列 (
  $A$ から任意に行を
  $0$ 本以上削除し、任意に列を
  $0$ 本以上削除した行列) は monotone である。

部分行列にはいろいろな定義があるみたいなので、明示しておきます。

行列

$A^{\prime }$ が行列

$A$ の部分行列であるとは、以下の条件が成り立つことをいう。

• $A$ から行を
  $0$ 本以上削除し、列を
  $0$ 本以上削除した結果
  $A^{\prime }$ を作ることができる。

同値な条件

行を削除しても monotone の条件が緩くなるだけなので、行の削除は考えなくて良いです。

ある列番号の集合

$J\subset \{1,2,\dots ,M\}$ が存在して、

$A$ から

$J$ 以外の列を削除した行列

$A^{\prime }$ が monotone でないと仮定します。
すなわち、ある

$i$ が存在して

$\mathrm{argmin}(A_i^{\prime })>\mathrm{argmin}(A_{i+1}^{\prime })$ ということです。

このとき、

$j_1=\mathrm{argmin}(A_{i+1}^{\prime })$ と

$j_2=\mathrm{argmin}(A_i^{\prime })$ の

$2$ 列のみを取ってきても、

$A_{i,j_1}^{\prime }>A_{i,j_2}^{\prime }$ かつ

$A_{i+1,j_1}^{\prime }<A_{i+1,j_2}^{\prime }$ なので monotone になっていません。
したがって、以下の同値な条件がわかります。

$N\times M$ 行列

$A$ が totally monotone であるとは、以下の条件が成り立つことをいう。

• $1\le i<i+1\le N$ および
  $1\le j_1<j_2\le M$ を満たすすべての整数の組
  $(i,j_1,j_2)$ について、行
  $i,i+1$ と列
  $j_1,j_2$ のみからなる部分行列が monotone
  $(A_{i,j_1}>A_{i,j_2}⟹A_{i+1,j_1}>A_{i+1,j_2})$ である。

つまり…？

$A_{i,j_1}$ と

$A_{i,j_2}$ を比較し、

$A_{i,j_1}>A_{i,j_2}$ であった場合 :

$$A_{i,j_1}>A_{i,j_2}⟹A_{i+1,j_1}>A_{i+1,j_2}⟹A_{i+2,j_1}>A_{i+2,j_2}⟹\cdots$$

$A_{i,j_1}<A_{i,j_2}$ であった場合 :

$$A_{i,j_1}<A_{i,j_2}⟹A_{i-1,j_1}<A_{i-1,j_2}⟹A_{i-2,j_1}<A_{i-2,j_2}⟹\cdots$$

と、連鎖的に大小が定まります。

Monge ならば totally monotone

$A$ が

$2\times 2$ Monge 行列のとき、Monge

$⟹$ monotone を示します。

Monge なので

$A_{2,2}-A_{2,1}\le A_{1,2}-A_{1,1}$ です。このとき

$\text{argmin}$ がどうなるかを見ると、

条件	$\mathrm{argmin}(A_1)$	$\mathrm{argmin}(A_2)$
$0<A_{2,2}-A_{2,1}\le A_{1,2}-A_{1,1}$	$1$	$1$
$A_{2,2}-A_{2,1}<0<A_{1,2}-A_{1,1}$	$1$	$2$
$A_{2,2}-A_{2,1}\le A_{1,2}-A_{1,1}<0$	$2$	$2$

なので

$A$ は monotone です。

$A$ が一般の行列のとき、

Monge

$⟹$ 任意の

$2\times 2$ 部分行列が Monge

$⟹$ 任意の

$2\times 2$ 部分行列が monotone

$⟹$ totally monotone

なので、Monge ならば totally monotone です。

行の中に同じ値が存在する場合

$A$ の各要素に列番号を付加 :

$A_{i,j}\mapsto (A_{i,j},j)$
をして、これの辞書順で大小を比較するようにすると、行の中で tie-break ができます。

$A$ が Monge ならば、

$$\begin{array}{rlrl}& & A_{i_1,j_1}+A_{i_2,j_2}& \le A_{i_1,j_2}+A_{i_2,j_1}\\ ⟹& & (A_{i_1,j_1}+A_{i_2,j_2},j_1+j_2)& \le (A_{i_1,j_2}+A_{i_2,j_1},j_1+j_2)\\ ⟹& & (A_{i_1,j_1},j_1)+(A_{i_2,j_2},j_2)& \le (A_{i_1,j_2},j_2)+(A_{i_2,j_1},j_1)\end{array}$$

より列番号を付加した状態でも Monge で、totally monotone であることがわかります。

totally monotone だけど Monge でないという問題を見たことがないので、totally monotone と Monge は同じものだと思ってしまって良いです。(本当に？)

1 つの 行 / 列 に値を加算しても Monge

Monge の条件式

$A_{i_1,j_1}+A_{i_2,j_2}\le A_{i_1,j_2}+A_{i_2,j_1}$ において、行

$i_1$ に定数

$c$ を加算しても、

$$(A_{i_1,j_1}+c)+A_{i_2,j_2}\le (A_{i_1,j_2}+c)+A_{i_2,j_1}$$

両辺に

$c$ が足されるだけなので変わりません。同様に、列

$j_1$ に定数

$c$ を加算しても、

$$(A_{i_1,j_1}+c)+A_{i_2,j_2}\le A_{i_1,j_2}+(A_{i_2,j_1}+c)$$

両辺に

$c$ が足されるだけなので変わりません。

合成しても Monge

Monge 行列

$A\in {\mathbb{R}}^{N\times M},B\in {\mathbb{R}}^{M\times K}$ に対し、

$C_{i,j}={\displaystyle \underset{k}{min}\{A_{i,k}+B_{k,j}\}}$ で定義される行列

$C$ は Monge です。

任意の

$i_1<i_2,j_1<j_2$ に対して

$$C_{i_1,j_1}+C_{i_2,j_2}\le C_{i_1,j_2}+C_{i_2,j_1}$$

を示したいです。これは、任意の

$k_1,k_2$ に対しある

$l_1,l_2$ が存在して、

$$(A_{i_1,l_1}+B_{l_1,j_1})+(A_{i_2,l_2}+B_{l_2,j_2})\le (A_{i_1,k_1}+B_{k_1,j_2})+(A_{i_2,k_2}+B_{k_2,j_1})$$

と同値です。

$k_1\le k_2$ のとき、Monge 性より

$B_{k_1,j_1}+B_{k_2,j_2}\le B_{k_1,j_2}+B_{k_2,j_1}$ なので、

$(l_1,l_2)=(k_1,k_2)$ を選ぶと不等式が成立します。

$k_1\ge k_2$ のとき、Monge 性より

$A_{i_1,k_2}+A_{i_2,k_1}\le A_{i_1,k_1}+A_{i_2,k_2}$ なので、

$(l_1,l_2)=(k_2,k_1)$ を選ぶと不等式が成立します。

Monge 行列の例

• 下に凸 な関数
  $f:\mathbb{Z}\to \mathbb{R}$ に対し、
  $A_{i,j}=f(j-i)$ で定義される行列
  $A$ は Monge です。

$$A_{i,j}+A_{i+1,j+1}-A_{i,j+1}-A_{i+1,j}=2f(j-i)-f(j-i-1)-f(j-i+1)$$

$f$ は下に凸なので

${\displaystyle f(j-i)\le \frac{f(j-i-1)+f(j-i+1)}{2}}$ であり、

$$\begin{gathered} A_{i,j}+A_{i+1,j+1}-A_{i,j+1}-A_{i+1,j}\le 0 \\ {A}_{i,j}+A_{i+1,j+1}\le A_{i,j+1}+A_{i+1,j} \end{gathered}$$

より Monge です。

• ${\displaystyle A_{i,j}=(j-i{)}^2+\sum _{k=i}^{j-1}{a}_k}$

$a$ の累積和を

${\displaystyle s_i=\sum _{k=1}^{i-1}{a}_k}$ とすると、

$A_{i,j}=(j-i{)}^2+s_j-s_i$ です。

$s_j$ と

$-s_i$ は 行 / 列 に加算しているので関係なく、

$(j-i{)}^2$ は

$j-i$ の凸関数なので、Monge です。

• Monge 行列
  $A$ と広義単調増加関数
  $f:\mathbb{N}\to \mathbb{N}$ に対し、
  $B_{i,j}=A_{i,f(j)}$ で定義される行列
  $B$ は Monge です。

$$B_{i_1,j_1}+B_{i_2,j_2}=A_{i_1,f(j_1)}+A_{i_2,f(j_2)}\le A_{i_1,f(j_2)}+A_{i_2,f(j_1)}=B_{i_1,j_2}+B_{i_2,j_1}$$

より Monge です。

同様に

$B_{i,j}=A_{f(i),j}$ でも Monge です。

• $A_{i,j}=(a_i-b_j{)}^2$ (
  $a,b$ は広義単調増加の整数列)

• $A_{i,j}^{″}=(i-j{)}^2$ は Monge です。
• $a$ は広義単調増加なので、
  $A_{i,j}^{\prime }=(a_i-j{)}^2$ は Monge です。
• $b$ も広義単調増加なので、
  $A_{i,j}=(a_i-b_j{)}^2$ は Monge です。
• (実数列でも Monge になります。)

• Monge 行列
  $A$ と実数
  $c\ge 0$ に対し、
  $B_{i,j}=c{A}_{i,j}$ で定義される行列
  $B$ は Monge です。
• Monge 行列
  $A,B$ に対し、
  $C_{i,j}=A_{i,j}+B_{i,j}$ で定義される行列
  $C$ は Monge です。
• $A_{i,j}=(B_i\mathrm{AND}{B}_{i+1}\mathrm{AND}\cdots \mathrm{AND}{B}_{j-1})$　(
  $\text{AND}$ は bitwise AND 演算)

$1$ つの bit で Monge であれば、bitwise AND はその線型結合なので Monge になります。
以下

$B_i\in \{0,1\}$ とします。

$$\begin{array}{rl}(A_{i+1,j}-A_{i+1,j+1})-(A_{i,j}-A_{i,j+1})& =A_{i+1,j}(1-B_j)-A_{i,j}(1-B_j)\\ & =(A_{i+1,j}-A_{i,j})(1-B_j)\\ & =A_{i+1,j}(1-B_i)(1-B_j)\\ & \ge 0\end{array}$$

より Monge です。

こんな計算をしなくても、「右端を

$j_1\to j_2$ と広げたときのコストの減少分」は、元々の区間

$[i,j_1]$ が長いほど小さい を確認すれば です。

参考文献

Knuth-Yao speedup - 週刊 spaghetti_source - TopCoder部