https://noshi91.hatenablog.com/entry/2023/02/18/005856

概要

LARSCH Algorithm の簡易版を思いついたので説明する。時間計算量 $\Theta(N \log(N) )$ だが実装や仕組みが単純で、コスト関数が sliding window でしか計算できない場合にも有用。

~~2024/03/13 追記: もっと簡単なアルゴリズムがあったのでこの記事はコストがスライドでしか高速に計算できないときにしか役に立たないと思います~~

2024/06/02 追記: 上記のアルゴリズムは、CHT (deque を使うもの) をそのまま Monge に拡張したアルゴリズムで、Monge / anti-Monge な行列と CHT / Li Chao Tree の関係 - Cyanmond - 競技プログラミングこの記事や No.705 ゴミ拾い Hard - yukicoder この問題の解説が詳しいです。これらのアルゴリズムの方が理解と実装がしやすいと思っていたのですが、最近の動向を見ると本記事のアルゴリズムの方が定数倍が良く実装もさほど難しくないと考えられているようです。

問題設定

$w$ を Monge なコスト関数として、

\begin{align} \text{dp} \lbrack i \rbrack = \begin{cases} 0 \quad & (i = 0) \cr \displaystyle \min _ {0 \leq k \lt i} \left( \text{dp} \lbrack k \rbrack + w(k, i) \right) \quad & (i \gt 0) \end{cases} \end{align}

で定義されるテーブルを $0 \leq i \leq N$ の範囲で計算したいことがよくある。 $A _ {i, k} := dp \lbrack k \rbrack + w(k, i)$ と定義すると、この問題は Monge 行列 $A$ の行最小値を求める問題と捉えられる*1。ただし、

$A$ は $\lbrack 0, N \rbrack \times \lbrack 0, N \rbrack$ 行列だが、対角部分を含まない下三角部分のみが存在する。
第 $i$ 行の行最小値を求めないと第 $i$ 列にアクセスできない。

という点で通常の行最小値の問題とは異なる。本記事ではこの問題をオンラインと呼び、通常の行最小値問題をオフラインと呼ぶ。

様々なアルゴリズム

Monge な行列に対する行最小値問題に関連するアルゴリズムをまとめた。

アルゴリズム	問題設定	時間計算量	アクセス	実装量
monotone minima	オフライン	$\Theta(N \log(N) )$	スライド	★
SMAWK Algorithm	オフライン	$\Theta(N)$	ランダム	★★★
分割統治 + monotone minima	オンライン	$\Theta(N (\log(N) ) ^ 2)$	スライド	★★
分割統治 + SMAWK Algorithm	オンライン	$\Theta(N \log(N) )$	ランダム	★★★
本記事で解説	オンライン	$\Theta(N \log(N) )$	スライド	★★
LARSCH Algorithm	オンライン	$\Theta(N)$	ランダム	★★★★

ランダムは $A$ にランダムアクセスする必要があるという意味で、スライドは Mo's Algorithm のように $A _ {i, k}$ から $A _ {i \pm 1, k \pm 1}$ への移動ができれば十分という意味。実装量はランダムアクセス版で主観で大雑把に評価した。

本題

ランダムアクセスできる場合

まずは $A$ にランダムアクセスできるものとしてアルゴリズムを説明する。

vector<ll> mini(N + 1, 1e18);
vector<int> amin(N + 1, 0);

void check(int i, int k) {
    if (A[i][k] < mini[i]) {
        mini[i] = A[i][k];
        amin[i] = k;
    }
}

void solve(int l, int r) {
    if (r - l == 1) return;
    int m = (l + r) / 2;
    for (int k = amin[l]; k <= amin[r]; k++) check(m, k);
    solve(l, m);
    for (int k = l + 1; k <= m; k++) check(r, k);
    solve(m, r);
}

int main() {
    check(N, 0);
    solve(0, N);
}

mini[i] は暫定的な第 $i$ 行の最小値、amin[i] はその最小値を達成する列番号を管理する。 check(i, k) は $A _ {i, k}$ を用いて暫定最小値を更新できるなら更新する関数。 solve(l, r) がこのアルゴリズムの本体であり、以下の事前条件と事後条件を持つ。

事前条件

$( 0 , l \rbrack$ 行の最小値は完全に計算済
第 $r$ 行の最小値が第 $\lbrack 0 , l \rbrack$ 列の範囲で計算済

事後条件

$(l, r \rbrack$ 行の最小値が完全に計算済

事前条件と事後条件が満たされるように再帰的呼び出しが行われていること、 $A _ {i, k}$ へのアクセスが第 $k$ 行の最小値が完全に計算された後に行われていることを確認せよ。

時間計算量を考える。最終的な amin[i] の値を $k ^ \ast _ i$ と置くと、solve(l, r) の時間計算量のうち再帰的な呼び出しを除く部分は $\Theta(r - l) + O( k ^ \ast _ r - k ^ \ast _ l)$ である。したがって、再帰的な呼び出しの各深さについて、その深さにおける時間計算量は $\Theta(N)$ である。深さは $\Theta(\log(N) )$ だから、全体で時間計算量は $\Theta(N \log(N) )$ である。

スライドでアクセスする場合

$A _ {i, k}$ の値を計算するために管理するデータをカーソルと呼ぶことにする。カーソルには $(i, k)$ が紐づいており、 $i$ や $k$ を $\pm 1$ する操作と、 $A _ {i, k}$ の値を取得する操作ができるものとする。

ランダムアクセスできる場合のコードに、グローバル変数として $2$ つのカーソル s, t を追加する。更に事前条件に「カーソル s は $(l, k ^ \ast _ l )$ を指しており、t は $(l, l)$ を指している。」という条件を追加し、事後条件に「s は $(r, k ^ \ast _ r)$ を指しており、t は $(r, r)$ を指している。」という条件を追加する。元のアルゴリズムにおける check(m, k) の部分をカーソル s で、check(r, k) の部分をカーソル t で計算するようにすれば、同じ時間計算量で計算できることが分かる。