Monge 行列と monotone minima について

Monge 行列や monotone minima について何も知らない方でも理解できるよう, 一から丁寧に解説する記事を書きました. 計算量解析については多少の前提知識を要求しますが, その他の部分については式を追っていけば理解できると思います.

本記事の評判次第ではありますが, 続編として SMAWK algorithm についての記事もいずれ書きたいと考えております.

Monge 行列の定義と性質

定義

$ m \times n $ 型実数値行列 $ A $ が, $ 1 \leq i \lt k \leq m $ および $ 1 \leq j \lt l \leq n $ を満たすすべての $ i, j, k, l $ について

A[i, j] + A[k, l] \leq A[i, l] + A[k, j]

を満たすとき, $ A $ を Monge 行列と呼ぶ.

つまり, Monge 行列から任意に 2 つの行と 2 つの列を取り, それらの行と列の交点で定まる 4 つの要素を考えたとき, 左上と右下の要素の和は左下と右上の要素の和以下である.

たとえば, 以下に示す行列は Monge 行列である.

\left( \begin{matrix} 10 \quad 17 \quad 13 \quad 28 \quad 23\\ 17 \quad 22 \quad 16 \quad 29 \quad 23\\ 24 \quad 28 \quad 22 \quad 34 \quad 24\\ 11 \quad 13 \quad \ \ 6 \quad 17 \quad \ \ 7\\ 45 \quad 44 \quad 32 \quad 37 \quad 23\\ 36 \quad 33 \quad 19 \quad 21 \quad \ \ 6\\ 75 \quad 66 \quad 51 \quad 53 \quad 34\\ \end{matrix} \right)

補題 1

ある $ m \times n $ 型行列 $ A $ が Monge 行列であるための必要十分条件は, $ 1 \leq i \lt m $ および $ 1 \leq j \lt n $ を満たすすべての $ i, j $ について

A[i, j] + A[i+1, j+1] \leq A[i, j+1] + A[i+1, j]

が成立することである.

証明

$ (\Rightarrow) $
Monge 行列の定義より明らかである.

$ (\Leftarrow) $
$ 1 \leq s \lt m $ および $ 1 \leq t \lt n $ を満たすすべての $ s, t $ について

A[s, t] + A[s+1, t+1] \leq A[s, t+1] + A[s+1, t]

であるとき, $ 1 \leq i \lt k \leq m $ を満たす $ i, k $ について $ s = i, \ldots, k - 1 $ として辺々加えて,

\sum _ {s=i} ^ {k-1} (A[s, t] + A[s+1, t+1]) \leq \sum _ {s=i} ^ {k-1} (A[s, t+1] + A[s+1, t]).

両辺ともに出現する項を消去し,

A[i, t] + A[k, t+1] \leq A[i, t+1] + A[k, t].

次に, $ 1 \leq j \lt l \leq n $ を満たす $ j, l $ について $ t = j, \ldots, l - 1 $ として辺々加えて, 式を整理すると,

\sum _ {t = j} ^ {l-1}(A[i, t] + A[k, t+1]) \leq \sum _ {t=j} ^ {l-1}(A[i, t+1] + A[k, t]);
A[i, j] + A[k, l] \leq A[i, l] + A[k, j].

以上より, $ A $ が Monge 行列であることが示された.

補題 2

$ f(i) $ を, 行 $ i $ の最小要素のうち最も左に位置するものの列番号とする. 任意の $ m \times n $ 型 Monge 行列において

f(1) \leq f(2) \leq \cdots \leq f(m)

が成り立つ.

証明

$ A $ を $ m \times n $ 型 Monge 行列として, $ 1 \leq i \lt m $ かつ $ f(i) \gt f(i + 1) $ を満たす $ i $ が存在すると仮定する.
$ A $ は Monge 行列であることから,

A[i, f(i + 1)] + A[i + 1, f(i)] \leq A[i, f(i)] + A[i + 1, f(i + 1)]\tag{1}

が成り立つ.
一方, $ f(i) $ は行 $ i $ における最左の最小要素の列番号であるため,

A[i, f(i + 1)] \gt A[i, f(i)].

$ f(i + 1) $ は行 $ i + 1 $ における最左の最小要素の列番号であるため,

A[i + 1, f(i)] \geq A[i + 1, f(i + 1)].

辺々加えて,

A[i, f(i + 1)] + A[i + 1, f(i)] \gt A[i, f(i)] + A[i + 1, f(i + 1)]\tag{2}

を得る.
式 $(1), (2)$ が同時に成り立つことはないため, $ 1 \leq i \lt m $ かつ $ f(i) \gt f(i + 1) $ を満たす $ i $ は存在しない.

以上より, 任意の $ m \times n $ 型 Monge 行列において

f(1) \leq f(2) \leq \cdots \leq f(m)

が成り立つことが示された.

補足

なお, $ m \times n $ 型行列 $ A $ について

f(1) \leq f(2) \leq \cdots \leq f(m)

が成り立つことを, monotone であるという.
さらに, $ A $ の任意の部分行列*1について monotone であるとき, $ A $ は totally monotone であるという.

Monge 行列が monotone であることは補題 2 で示しており, $ A $ が Monge 行列であるとき, $ A $ の任意の部分行列も明らかに Monge 行列であるので, 任意の Monge 行列は totally monotone である.

つまり, 「$ A $ が Monge 行列 $ \Rightarrow $ $ A $ は totally monotone $ \Rightarrow $ $ A $ は monotone」という関係が成り立っており, $ A $ が Monge 行列であることは totally monotone であることや monotone であることよりも"強い"条件であるといえる.

monotone minima

monotone minima とは, monotone な行列について各行の最小要素のうち最も左に位置するものの列番号, すなわち補題 2 における $ f(i) $ を効率よく求める分割統治アルゴリズムである.

アルゴリズムの解説

$ A $ を $ m \times n $ 型の monotone な行列とする. monotone minima の概要は以下の通りである.

  1. $ A $ の偶数行だけ取り出して $ A $ の部分行列 $ A' $ を作る.
  2. $ A' $ に対して再帰的にアルゴリズムを適用し, 各行における最左の最小要素の列番号を求める.
  3. $ A $ の奇数行における最左の最小要素の列番号を求める.

まず, $ A $ の偶数行の最左の最小要素の列番号が分かっているという仮定のもとで, $ A $ の奇数行の最左の最小要素の列番号を $ O(m+n) $ 時間で求める方法を解説する.

番兵として $ f(0) = 1, f(m+1) = n $ と定義すると, $0 \leq k \lt \left\lceil m/2 \right\rceil $ を満たす $ k $ に対して $ f(2k+1) $ を求めるには, $ A $ が monotone であることより, $ 2k+1 $ 行目の $ f(2k) $ 列目から $ f(2k+2) $ 列目までを線形探索すればよい.
$ 1 \leq j \leq n $ を満たす各 $ j $ に対して, $ 1 \leq i \leq m $ かつ $ f(i) = j $ を満たす偶数 $ i $ の個数を $ N _ j $ と表すと, $ j $ 列目の数が探索される回数は $ N _ j + 1 $ 回である. $ \sum _ {j=1} ^ {n}{N_j} = \left\lfloor m/2 \right\rfloor $ であることに注意し, 合計探索回数は $ \sum _ {j=1} ^ {n}{\left( N_j + 1 \right)} = \left\lfloor m/2 \right\rfloor + n $ と求められる.
以上より, ステップ 3. の時間計算量が $ O(m + n) $ であることが示された.

次に, このアルゴリズム全体の時間計算量を解析する.
$ m \times n $ 型の行列に対して monotone minima を適用したときの最悪実行時間を $ T(m, n) $ とおく. 再帰のベースケースとして $ m = 1 $ のときの最悪実行時間は $ O(n) $ であり, $ m \times n $ 型行列に対する問題は $ \left\lfloor m/2 \right\rfloor \times n $ 型行列に対する問題と $ O(m+n) $ 時間の処理に帰着されるので, 以下の漸化式が得られる.

\left\{ \begin{aligned} T(1, n) &= O(n), \\ T(m, n) &= T(\left\lfloor m/2 \right\rfloor, n) + O(m + n). \\ \end{aligned} \right.

よって, ある定数 $ c _ 1 , c _ 2 > 0 $ が存在して, すべての $ m, n $ について以下の不等式が成り立つ.

\left\{ \begin{aligned} T(1, n) &\leq c _ 1 n, \\ T(m, n) &\leq T(\left\lfloor m/2 \right\rfloor, n) + c _ 2(m + n). \\ \end{aligned} \right. \tag{3}

この漸化式の解を $ T(m, n) = O(m + n \lg{m}) $ であると推定する. *2
ここで $ c $ を, すべての $ n $ について以下の条件を満たすようにとる.

\left\{ \begin{aligned} c_2 &\leq \frac{1}{2}c, \\ T(2, n) &\leq c(2 + n\lg{2}), \\ T(3, n) &\leq c(3 + n\lg{3}). \\ \end{aligned} \right.

そのような $ c $ の存在は, 式 $(3)$ に従い $T(2, n), T(3, n)$ を変形すれば示せる.
以下, すべての $m \geq 2, n $ について $ T(m, n) \leq c(m + n \lg{m})$ が成り立つことを帰納法で示す.

$ m = 2, 3 $ のとき, $ c $ の定義より明らか.
$ m \geq 4$ のとき,

\begin{aligned} T(m, n) &\leq T\left(\left\lfloor \frac{m}{2} \right\rfloor, n\right) + c_2(m + n)\\ &\leq c\left(\left\lfloor \frac{m}{2} \right\rfloor + n \lg{\left\lfloor \frac{m}{2} \right\rfloor}\right)+ c _ 2(m + n) \\ &\leq c\left(\frac{m}{2}+ n \lg\frac{m}{2}\right)+ c _ 2(m + n) \\ &\leq c\left(\frac{m}{2} + n \lg\frac{m}{2}\right)+ \frac{1}{2}cm + cn \\ &\leq c(m + n \lg{m}).\\ \end{aligned}

以上より, ある定数 $ c > 0 $ が存在して, すべての $m \geq 2, n$ に対して $ T(m, n) \leq c(m + n \lg{m})$ が成り立つ.
したがって, アルゴリズム全体の時間計算量は $ O(m + n \lg{m}) $ である.

補足

本記事で紹介した monotone minima のアルゴリズムは, Monotone minima | Kyopro Encyclopedia of Algorithms においてその他の変種として扱われているものに相当する.
ただし, 本記事で紹介した monotone minima のアルゴリズムはより発展的なアルゴリズムである SMAWK algorithm のサブルーチンに相当するため, 今後 SMAWK algorithm についての記事を執筆することを念頭に置き, 変種として扱われている方を解説することとした.

実装例

実装上, 行列 $ A $ を陽に保持すると, それだけで空間計算量が $ \Theta (mn)$ となり, それに伴い時間計算量も $ \Omega (mn)$ となってしまうため, $ A $ は陰に保持されるべき*3である点に注意を要する.

引数 select の定義は,
select(i, j, k) $ := $ $ A[i, j] $ と $ A[i, k] $ $ (j < k) $ を比較して, 前者を選ぶ場合 false , 後者を選ぶ場合true
としている.

なお, 以下の実装方針は熨斗袋 (@noshi91) さんの SMAWK Algorithm の実装を参考にした.

#include <functional>
#include <numeric>
#include <vector>

template <class Select>
std::vector<size_t> monotone_minima(const size_t row_size,
                                    const size_t col_size,
                                    const Select& select) {
    using vec_zu = std::vector<size_t>;

    const std::function<vec_zu(const vec_zu&)> solve =
            [&](const vec_zu& row) -> vec_zu {
        const size_t m = row.size();
        if (m == 0) return {};
        vec_zu row2;
        for (size_t i = 1; i < m; i += 2) row2.push_back(row[i]);
        const vec_zu ans2 = solve(row2);
        vec_zu ans(m);
        for (size_t i = 0; i < ans2.size(); ++i) ans[2 * i + 1] = ans2[i];
        size_t j = 0;
        for (size_t i = 0; i < m; i += 2) {
            ans[i] = j;
            const size_t end = (i + 1 == m ? col_size - 1 : ans[i + 1]);
            while (j != end) {
                j++;
                if (select(row[i], ans[i], j)) ans[i] = j;
            }
        }
        return ans;
    };

    vec_zu row(row_size);
    std::iota(row.begin(), row.end(), 0);
    return solve(row);
}

例題

読者への課題とする.
atcoder.jp

ヒント↓ （反転せよ.）
行列 $ A $ を
$ A[i, j] := i $ 番のすぬけキャノンでけぬす号の区画 $ j $ を破壊するために必要なエネルギー
と定義すると, $ A $ はどのような性質を持つか.

参考リンク

参考文献

  • Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009.

謝辞

本記事公開前に, えびちゃん (@rsk0315_h4x) さんにレビューと校正をしていただきました. また, monotone minima の時間計算量の解析について, 熨斗袋 (@noshi91) さんにご教授いただきました. ありがとうございました.

*1:https://ja.wikipedia.org/wiki/%E5%B0%8F%E8%A1%8C%E5%88%97

*2:再帰木法などでよしなに.

*3:$i, j$ を渡すと $ A[i, j] $ の値を返す関数が用意されている状況などを想定されたい.