cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub rniya/cp-library

:heavy_check_mark: Min Plus Convolution (Convex and Arbitary)
(src/convolution/min_plus_convolution_convex_arbitrary.hpp)

入力

数列 $a, b$

ここで数列 $a$ は下に凸である． すなわち，任意の $0 \leq i \lt N - 2$ に対して $a _ {i + 1} - a _ i \leq a _ {i + 2} - a _ {i + 1}$ が成立する．

2 つの数列の長さをそれぞれ $n, m$ とする．

出力

数列 $a$ と $b$ の畳み込み． すなわち，

\[c _ k = \min _ {i + j = k} (a _ i + b _ j)\]

で定義される長さ $n + m - 1$ の数列 $c$．

計算量

時間計算量 $\mathrm{O}((n + m) \log (n + m))$

概要

$(n + m - 1) \times m$ 行列 $X$ を

\[X _ {i, j} := a _ {i - j} + b _ j\]

により定めたとき，$X$ は totally monotone であり，monotone minima（時間計算量では SMAWK algorithm に劣るが，実用上はこちらの方が高速なのでこちらを採用している）により各行の最小値，すなわち所望の数列 $c$ を計算することが可能となる． ここで，$i \lt 0$ や $n \leq i$ に対する $a_i$ は $a$ の凸性を保つような十分大きい値を取るとする．

totally monotone であることの証明
$X$ の任意の $2$ 次正方部分行列が monotone であることを示せば良い． $X$ の行 $i, i ^ \prime\ (i \lt i ^ \prime)$ 及び列 $j, j ^ \prime\ (j \lt j ^ \prime)$ を取り出した部分行列を考える． $X _ {i, j} > X _ {i, j ^ \prime} \implies X _ {i ^ \prime, j} \gt X _ {i ^ \prime, j ^ \prime}$ を示せば十分だが，これは $i \lt i ^ \prime$ より， $$ 0 \lt X _ {i, j} - X _ {i, j ^ \prime} = a _ {i - j} - a _ {i - j ^ \prime} \leq a _ {i ^ \prime - j} - a _ {i ^ \prime - j ^ \prime} = X _ {i ^ \prime, j} - X _ {i ^ \prime, j ^ \prime} $$ だから成立する． $\blacksquare$

出題例

The 2nd Universal Cup. Stage 3: Binjiang L. Partially Free Meal

Depends on

Verified with

Code

#pragma once
#include <cassert>
#include "../optimization/monotone_minima.hpp"

template <typename T>
std::vector<T> min_plus_convolution_convex_arbitrary(const std::vector<T>& a, const std::vector<T>& b) {
    int n = a.size(), m = b.size();
    assert(n and m);
    for (int i = 0; i + 2 < n; i++) assert(a[i + 1] - a[i] <= a[i + 2] - a[i + 1]);
    auto f = [&](int i, int j) { return a[i - j] + b[j]; };
    auto select = [&](int i, int j, int k) {
        if (i < k) return false;
        if (n <= i - j) return true;
        return f(i, j) >= f(i, k);
    };
    auto argmin = monotone_minima(n + m - 1, m, select);
    std::vector<T> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) c[i] = f(i, argmin[i]);
    return c;
}
#line 2 "src/convolution/min_plus_convolution_convex_arbitrary.hpp"
#include <cassert>
#line 2 "src/optimization/monotone_minima.hpp"
#include <vector>

template <class Select> std::vector<int> monotone_minima(int n, int m, const Select& select) {
    std::vector<int> res(n);
    auto dfs = [&](auto self, int u, int d, int l, int r) -> void {
        if (u == d) return;
        int m = (u + d) >> 1;
        int argmin = l;
        for (int col = l + 1; col < r; col++) {
            if (select(m, argmin, col)) {
                argmin = col;
            }
        }
        res[m] = argmin;
        self(self, u, m, l, argmin + 1);
        self(self, m + 1, d, argmin, r);
    };
    dfs(dfs, 0, n, 0, m);
    return res;
}
#line 4 "src/convolution/min_plus_convolution_convex_arbitrary.hpp"

template <typename T>
std::vector<T> min_plus_convolution_convex_arbitrary(const std::vector<T>& a, const std::vector<T>& b) {
    int n = a.size(), m = b.size();
    assert(n and m);
    for (int i = 0; i + 2 < n; i++) assert(a[i + 1] - a[i] <= a[i + 2] - a[i + 1]);
    auto f = [&](int i, int j) { return a[i - j] + b[j]; };
    auto select = [&](int i, int j, int k) {
        if (i < k) return false;
        if (n <= i - j) return true;
        return f(i, j) >= f(i, k);
    };
    auto argmin = monotone_minima(n + m - 1, m, select);
    std::vector<T> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) c[i] = f(i, argmin[i]);
    return c;
}
Back to top page