Monotone minima （Monotone な行列の行最小値の効率的な探索）
(other_algorithms/monotone_minima.hpp)

• View this file on GitHub
• Last update: 2025-08-24 23:54:21+09:00
• Include: #include "other_algorithms/monotone_minima.hpp"
• Link: https://mofecoder.com/contests/monoxercon_202508/tasks/monoxercon_202508_k
• Link: https://topcoder-g-hatena-ne-jp.jag-icpc.org/spaghetti_source/20120923/1348327542.html

SMAWK() 関数は，monotone な $N \times M$ 行列，すなわち各行の最小値の位置が行を下るにつれ右に移動していくような行列について，各行の最小値の位置およびその値を $O((N + M) \log (N + M))$ で取得する．

SMAWK のライブラリと互換性があり，SMAWK が使用されている箇所は本関数で代替可能（最悪計算量のオーダーはこちらの方に log がつくが，問題によってはこちらの方が実測上速い）．

使用方法

例えば辺重みが Monge な $N$ 頂点の DAG で頂点 $0$ から各頂点への最短路重みを求めたいとき， $N$ 行 $N - 1$ 列の行列を $(j, i)$ 成分が「直前に頂点 $i$ を経由し頂点 $j$ に到達する場合の最短路重み」であるようなものとして定めると本関数が適用できる（SMAWK も適用できるが）．

using T = long long;
T inf = 1LL << 60;
int N;
vector<T> dp(N, inf);
dp[0] = 0;

auto weight = [&](int s, int t) -> T { /* Implement */ };

const auto res = MonotoneMinima<T>(
    N, N - 1, [&](int j, int i) -> T { return i < j ? dp[i] + weight(i, j) : inf; });

問題例

• K. Coupon - Monoxer Programming Contest for Engineers

Links

• Totally Monotone Matrix Searching (SMAWK algorithm) - 週刊 spaghetti_source - TopCoder部

Code

#pragma once
#include <cassert>
#include <functional>
#include <vector>

// finding minimum element for each row of N*M matrix
// Constraints: the solution is monotonically non-decreasing
// Complexity: O(NM logM)
// Reference:
// https://topcoder-g-hatena-ne-jp.jag-icpc.org/spaghetti_source/20120923/1348327542.html
// Verify: https://mofecoder.com/contests/monoxercon_202508/tasks/monoxercon_202508_k
template <class T>
std::vector<std::pair<int, T>>
MonotoneMinima(int N, int M, const std::function<T(int i, int j)> &weight) {
    std::vector<std::pair<int, T>> minima(N);

    auto rec = [&](auto &&self, int il, int ir, int jl, int jr) -> void {
        if (il >= ir or jl >= jr) return;
        const int im = (il + ir) / 2;
        T w = weight(im, jl);
        int j_argmin = jl;
        for (int j = jl + 1; j < jr; ++j) {
            if (T wt = weight(im, j); wt < w) w = wt, j_argmin = j;
        }
        minima[im] = {j_argmin, w};
        self(self, il, im, jl, j_argmin + 1);
        self(self, im + 1, ir, j_argmin, jr);
    };
    rec(rec, 0, N, 0, M);

    return minima;
}

#line 2 "other_algorithms/monotone_minima.hpp"
#include <cassert>
#include <functional>
#include <vector>

// finding minimum element for each row of N*M matrix
// Constraints: the solution is monotonically non-decreasing
// Complexity: O(NM logM)
// Reference:
// https://topcoder-g-hatena-ne-jp.jag-icpc.org/spaghetti_source/20120923/1348327542.html
// Verify: https://mofecoder.com/contests/monoxercon_202508/tasks/monoxercon_202508_k
template <class T>
std::vector<std::pair<int, T>>
MonotoneMinima(int N, int M, const std::function<T(int i, int j)> &weight) {
    std::vector<std::pair<int, T>> minima(N);

    auto rec = [&](auto &&self, int il, int ir, int jl, int jr) -> void {
        if (il >= ir or jl >= jr) return;
        const int im = (il + ir) / 2;
        T w = weight(im, jl);
        int j_argmin = jl;
        for (int j = jl + 1; j < jr; ++j) {
            if (T wt = weight(im, j); wt < w) w = wt, j_argmin = j;
        }
        minima[im] = {j_argmin, w};
        self(self, il, im, jl, j_argmin + 1);
        self(self, im + 1, ir, j_argmin, jr);
    };
    rec(rec, 0, N, 0, M);

    return minima;
}

Back to top page