---
tags: 競プロ
---
# [Monge まとめ①] Monge 性とは？
## まえがき
LARSCH の読んだので解説記事を書こうと思ったが、説明が難しくてなかなか書けない…
Monge を理解していきたいので Monge の記事を書きます。
完全に理解しているわけではないのでご了承ください。
## Monge の読み方
もんげ〜 と読みます。嘘です。
## Monge の定義
実数からなる $N \times M$ 行列について考えます。
:::info
$N \times M$ 行列 $A$ が Monge であるとは、以下の条件が成り立つことをいう。
- $1 ≤ i_1 < i_2 ≤ N$ および $1 ≤ j_1 < j_2 ≤ M$ を満たすすべての整数の組 $(i_1, i_2, j_1, j_2)$ について、$A_{i_1,j_1} + A_{i_2, j_2} ≤ A_{i_1,j_2} + A_{i_2, j_1}$ である。
:::
[ABC224-B Mongeness](https://atcoder.jp/contests/abc224/tasks/abc224_b)
上三角 / 下三角 バージョンもよくでてきますね。
### 上三角バージョン
:::info
$N \times N$ 行列 $A$ は 上三角 ( $i > j$ ならば無効値) であるものとする。このとき、上の条件は以下のように言い換えられる。
- $1 ≤ i_1 < i_2 ≤ j_1 < j_2 ≤ N$ を満たすすべての整数の組 $(i_1, i_2, j_1, j_2)$ について、$A_{i_1,j_1} + A_{i_2, j_2} ≤ A_{i_1,j_2} + A_{i_2, j_1}$ である。
:::
これは、無効値の部分を Monge になるように適当な値で埋め、さらに十分大きな定数 $\textit{INF}$ を用いて、無効値だった部分 $(i > j)$ の各要素に $\textit{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)$ で求められます。](https://noshi91.github.io/algorithm-encyclopedia/d-edge-shortest-path-monge)
- $A$ が Monge かつ単調 (区間が長いほど大きい) であるとき、区間 DP $\text{dp}[i][j] = \displaystyle\min_{i<k<j}\{\text{dp}[i][k] + \text{dp}[k][j]\} + A_{i,j}$ が $O(N^2)$ で計算できます。
- ほかいろいろ
### Monge のおきもち
私なりの理解です。
ちょっと式変形してみましょう。
$$
\begin{aligned}
A_{i_1,j_1} + A_{i_2, j_2} &≤ A_{i_1,j_2} + A_{i_2, j_1}\\
A_{i_2, j_2} - A_{i_2, j_1} &≤ A_{i_1,j_2} - A_{i_1,j_1}\\
\end{aligned}
$$
ここで、$A_{i_2, j_2} - A_{i_2, j_1}$ とは、「区間 $[i_2, j_1]$ の左端を固定し、右端を $j_1 → j_2$ と広げたときのコストの増分」と解釈できます。
$A_{i_1, j_2} - A_{i_1, j_1}$ も同様に、「区間 $[i_1, j_1]$ の左端を固定し、右端を $j_1 → j_2$ と広げたときのコストの増分」と解釈できます。
したがってこの式は、**「右端を $j_1 → j_2$ と広げたときのコストの増分」は、元々の区間 $[i, j_1]$ が長いほど大きい** ことを表しています。
つまり、こうです。
$$
A_{i,j_2} - A_{i,j_1} ≤ A_{i-1,j_2} - A_{i-1,j_1} ≤ A_{i-2,j_2} - A_{i-2,j_1} ≤ A_{i-3,j_2} - A_{i-3,j_1} ≤ \cdots
$$
---
左端を広げる場合も同様です。
$$
\begin{aligned}
A_{i_1,j_1} + A_{i_2, j_2} &≤ A_{i_1,j_2} + A_{i_2, j_1}\\
A_{i_1, j_1} - A_{i_2, j_1} &≤ A_{i_1, j_2} - A_{i_2, j_2}\\
\end{aligned}
$$
とすれば、**「左端を $i_2 → i_1$ と広げたときのコストの増分」は、元々の区間 $[i_2, j]$ が長いほど大きい** ことも表しています。
つまり、こうです。
$$
A_{i_1, j} - A_{i_2, j} ≤ A_{i_1, j + 1} - A_{i_2, j + 1} ≤ A_{i_1, j + 2} - A_{i_2, j + 2} ≤ A_{i_1, j + 3} - A_{i_2, j + 3}
$$
## 同値な条件
これをふまえると、以下の同値な条件がわかります。
:::info
$N \times M$ 行列 $A$ が Monge であるとは、以下の条件が成り立つことをいう。
- $1 ≤ i < i + 1 ≤ N$ および $1 ≤ j < j + 1 ≤ M$ を満たすすべての整数の組 $(i, j)$ について、$A_{i,j} + A_{i + 1, j + 1} ≤ A_{i + 1,j} + A_{i, j + 1}$ である。
:::
:::warning
**証明**
$A_{i_1,j_1} + A_{i_2, j_2} ≤ A_{i_1,j_2} + A_{i_2, j_1}$ の方を (A) 、$A_{i,j} + A_{i + 1, j + 1} ≤ A_{i + 1,j} + A_{i, j + 1}$ の方を (B) とします。
(A)$\implies$(B) は明らかなので、(B)$\implies$(A) を示せばよいです。
(B) を $A_{i + 1, j + 1} - A_{i, j + 1} ≤ A_{i + 1, j} - A_{i, j}$ と変形すると、
$$
A_{i + 1, j_2} - A_{i, j_2} ≤A_{i + 1, j_2 - 1} - A_{i, j_2 - 1} ≤ \dots ≤ A_{i + 1, j_1 + 1} - A_{i, j_1 + 1} ≤ A_{i + 1, j_1} - A_{i, j_1}
$$
より $A_{i + 1, j_2} + A_{i, j_1} ≤ A_{i + 1, j_1} + A_{i, j_2}$ です。
また、これを $A_{i + 1, j_2} - A_{i + 1, j_1} ≤ A_{i, j_2} - A_{i, j_1}$ と変形すると、
$$
A_{i_2, j_2} - A_{i_2, j_1} ≤ A_{i_2 - 1, j_2} - A_{i_2 - 1, j_1} ≤ \dots ≤ A_{i_1 + 1, j_2} - A_{i_1 + 1, j_1} ≤ A_{i_1, j_2} - A_{i_1, j_1}
$$
より $A_{i_1,j_1} + A_{i_2, j_2} ≤ A_{i_1,j_2} + A_{i_2, j_1}$ が示せました。
:::
## Monge 行列の性質
#### 転置しても Monge
定義の $i, j$ が対称な形なので、$i, j$ を入れ替えれば転置しても Monge であることがわかります。
#### 部分行列も Monge
Monge 行列 $A$ から、任意に行を $0$ 本以上削除し、任意に列を $0$ 本以上削除した行列 $A'$ を考えると、これも Monge です。
定義が、$A$ から任意の $2$ 行 $2$ 列を取り出すと $A_{i_1,j_1} + A_{i_2, j_2} ≤ A_{i_1,j_2} + A_{i_2, j_1}$ である という形なので、$A'$ から取り出しても成り立ちます。
#### Monge ならば totally monotone
まずは monotone から定義していきましょう。
### monotone
:::info
行ベクトル $v$ に対して、$\operatorname{argmin}(v)$ を $\min(v) = v_j$ なる $j$ と定義する。ただし、同じ値が複数ある場合は適切に tie-break し、同じ値が存在しないようにする。これにより $\min(v) = v_j$ なる $j$ は一意に定まる。
$N \times M$ 行列 $A$ が monotone であるとは、以下の条件が成り立つことをいう。
- $\operatorname{argmin}(A_1) ≤ \operatorname{argmin}(A_2) ≤ \dots ≤ \operatorname{argmin}(A_N)$
:::
### totally monotone
:::info
$N \times M$ 行列 $A$ が totally monotone であるとは、以下の条件が成り立つことをいう。
- $A$ の任意の部分行列 ($A$ から任意に行を $0$ 本以上削除し、任意に列を $0$ 本以上削除した行列) は monotone である。
:::
部分行列にはいろいろな定義があるみたいなので、明示しておきます。
:::info
行列 $A'$ が行列 $A$ の部分行列であるとは、以下の条件が成り立つことをいう。
- $A$ から行を $0$ 本以上削除し、列を $0$ 本以上削除した結果 $A'$ を作ることができる。
:::
#### 同値な条件
行を削除しても monotone の条件が緩くなるだけなので、行の削除は考えなくて良いです。
ある列番号の集合 $J \subset \{1, 2, …, M\}$ が存在して、$A$ から $J$ 以外の列を削除した行列 $A'$ が monotone でないと仮定します。
すなわち、ある $i$ が存在して $\operatorname{argmin}(A'_i) > \operatorname{argmin}(A'_{i+1})$ ということです。
このとき、$j_1 = \operatorname{argmin}(A'_{i+1})$ と $j_2 = \operatorname{argmin}(A'_i)$ の $2$ 列のみを取ってきても、$A'_{i,j_1} > A'_{i,j_2}$ かつ $A'_{i+1,j_1} < A'_{i+1,j_2}$ なので monotone になっていません。
したがって、以下の同値な条件がわかります。
:::info
$N \times M$ 行列 $A$ が totally monotone であるとは、以下の条件が成り立つことをいう。
- $1 ≤ i < i + 1 ≤ N$ および $1 ≤ j_1 < j_2 ≤ M$ を満たすすべての整数の組 $(i, j_1, j_2)$ について、行 $i, i + 1$ と列 $j_1, j_2$ のみからなる部分行列が monotone $(A_{i,j_1} > A_{i,j_2} \implies 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} \implies A_{i+1, j_1} > A_{i+1, j_2} \implies A_{i+2, j_1} > A_{i+2, j_2} \implies \cdots
$$
$A_{i, j_1} < A_{i, j_2}$ であった場合 :
$$
A_{i, j_1} < A_{i, j_2} \implies A_{i-1, j_1} < A_{i-1, j_2} \implies A_{i-2, j_1} < A_{i-2, j_2} \implies \cdots
$$
と、連鎖的に大小が定まります。
#### Monge ならば totally monotone
$A$ が $2 \times 2$ Monge 行列のとき、Monge $\implies$ monotone を示します。
:::warning
Monge なので $A_{2,2} - A_{2,1} ≤ A_{1,2} - A_{1,1}$ です。このとき $\text{argmin}$ がどうなるかを見ると、
| 条件 | $\operatorname{argmin}(A_1)$ | $\operatorname{argmin}(A_2)$ |
|:-------------------------------------------:|:----------------------------:|:----------------------------:|
| $0 < A_{2,2} - A_{2,1} ≤ 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} ≤ A_{1,2} - A_{1,1} < 0$ | $2$ | $2$ |
なので $A$ は monotone です。
:::
$A$ が一般の行列のとき、
Monge $\implies$ 任意の $2 \times 2$ 部分行列が Monge $\implies$ 任意の $2 \times 2$ 部分行列が monotone $\implies$ totally monotone
なので、Monge ならば totally monotone です。
#### 行の中に同じ値が存在する場合
$A$ の各要素に列番号を付加 : $A_{i,j} \mapsto (A_{i,j}, j)$
をして、これの辞書順で大小を比較するようにすると、行の中で tie-break ができます。
$A$ が Monge ならば、
$$
\begin{aligned}
&&A_{i_1,j_1} + A_{i_2, j_2} &≤ A_{i_1,j_2} + A_{i_2, j_1}\\
\implies&&(A_{i_1,j_1} + A_{i_2, j_2}\,,\,j_1 + j_2) &≤ (A_{i_1,j_2} + A_{i_2, j_1}\,,\,j_1 + j_2)\\
\implies&&(A_{i_1,j_1}, j_1) + (A_{i_2, j_2}, j_2) &≤ (A_{i_1,j_2}, j_2) + (A_{i_2, j_1}, j_1)\\
\end{aligned}
$$
より列番号を付加した状態でも Monge で、totally monotone であることがわかります。
totally monotone だけど Monge でないという問題を見たことがないので、totally monotone と Monge は同じものだと思ってしまって良いです。(本当に？)
#### 1 つの 行 / 列 に値を加算しても Monge
Monge の条件式 $A_{i_1,j_1} + A_{i_2, j_2} ≤ A_{i_1,j_2} + A_{i_2, j_1}$ において、行 $i_1$ に定数 $c$ を加算しても、
$$
(A_{i_1,j_1} + c) + A_{i_2, j_2} ≤ (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} ≤ 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\min_k\{A_{i,k} + B_{k,j}\}$ で定義される行列 $C$ は Monge です。
:::warning
任意の $i_1 < i_2,\ j_1 < j_2$ に対して
$$
C_{i_1, j_1} + C_{i_2, j_2} ≤ 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}) ≤ (A_{i_1,k_1} + B_{k_1,j_2}) + (A_{i_2,k_2} + B_{k_2,j_1})
$$
と同値です。
$k_1 ≤ k_2$ のとき、Monge 性より $B_{k_1,j_1} + B_{k_2,j_2} ≤ B_{k_1,j_2} + B_{k_2,j_1}$ なので、$(l_1, l_2) = (k_1, k_2)$ を選ぶと不等式が成立します。
$k_1 ≥ k_2$ のとき、Monge 性より $A_{i_1,k_2} + A_{i_2,k_1} ≤ A_{i_1,k_1} + A_{i_2,k_2}$ なので、$(l_1, l_2) = (k_2, k_1)$ を選ぶと不等式が成立します。
:::
## Monge 行列の例
- [下に凸](https://ja.wikipedia.org/wiki/%E5%87%B8%E9%96%A2%E6%95%B0) な関数 $f : \mathbb Z \to \mathbb R$ に対し、$A_{i,j} = f(j - i)$ で定義される行列 $A$ は Monge です。
:::warning
$$
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) ≤ \frac{f(j - i - 1) + f(j - i + 1)}{2}$ であり、
$$
A_{i,j} + A_{i+1,j+1} - A_{i,j+1} - A_{i+1,j} ≤ 0\\
A_{i,j} + A_{i+1,j+1} ≤ A_{i,j+1} + A_{i+1,j}\\
$$
より Monge です。
:::
- [$\displaystyle A_{i,j} = (j - i)^2 + \sum_{k = i}^{j - 1} a_k$](https://yukicoder.me/problems/no/913)
:::warning
$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 です。
:::warning
$$
B_{i_1,j_1} + B_{i_2,j_2} = A_{i_1,f(j_1)} + A_{i_2,f(j_2)} ≤ 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$ は広義単調増加の整数列)
:::warning
- $A''_{i,j} = (i - j)^2$ は Monge です。
- $a$ は広義単調増加なので、$A'_{i,j} = (a_i - j)^2$ は Monge です。
- $b$ も広義単調増加なので、$A_{i,j} = (a_i - b_j)^2$ は Monge です。
- (実数列でも Monge になります。)
:::
- Monge 行列 $A$ と実数 $c ≥ 0$ に対し、$B_{i,j} = cA_{i,j}$ で定義される行列 $B$ は Monge です。
- Monge 行列 $A,B$ に対し、$C_{i,j} = A_{i,j} + B_{i,j}$ で定義される行列 $C$ は Monge です。
- $A_{i,j} = (B_i\,\operatorname{AND}\,B_{i+1}\,\operatorname{AND}\,\cdots\,\operatorname{AND}\,B_{j-1})$ ($\text{AND}$ は bitwise AND 演算)
:::warning
$1$ つの bit で Monge であれば、bitwise AND はその線型結合なので Monge になります。
以下 $B_i \in \{0, 1\}$ とします。
$$
\begin{aligned}
(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)\\
&≥ 0\\
\end{aligned}
$$
より Monge です。
こんな計算をしなくても、**「右端を $j_1 → j_2$ と広げたときのコストの減少分」は、元々の区間 $[i, j_1]$ が長いほど小さい** を確認すれば :ok: です。
:::
### 参考文献
[Knuth-Yao speedup - 週刊 spaghetti_source - TopCoder部](https://topcoder-g-hatena-ne-jp.jag-icpc.org/spaghetti_source/20120915/1347668163.html)
Sign in with Wallet
Connect another wallet