Min Plus Convolution (Convex and Convex)
(src/convolution/min_plus_convolution_convex_convex.hpp)

• View this file on GitHub
• Last update: 2024-06-01 02:28:17+09:00
• Include: #include "src/convolution/min_plus_convolution_convex_convex.hpp"

入力

数列 $a, b$

ここで数列 $a, b$ はどちらも下に凸である． すなわち，任意の $0 \leq i \lt N - 2$ に対して $a _ {i + 1} - a _ i \leq a _ {i + 2} - a _ {i + 1},\ b _ {i + 1} - b _ i \leq b _ {i + 2} - b _ {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)$

概要

線分の傾きをマージすることで $\mathrm{O}(n + m)$ 時間で計算可能である． また，畳み込んでできる数列 $c$ も凸である．

Verified with

• test/yosupo/min_plus_convolution_convex_convex.test.cpp

Code

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

template <typename T>
std::vector<T> min_plus_convolution_convex_convex(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]);
    for (int i = 0; i + 2 < m; i++) assert(b[i + 1] - b[i] <= b[i + 2] - b[i + 1]);
    std::vector<T> c(n + m - 1);
    c[0] = a[0] + b[0];
    for (int i = 0, j = 0, k = 1; k < n + m - 1; k++) {
        if (j == m - 1 or (i < n - 1 and a[i + 1] + b[j] < a[i] + b[j + 1]))
            c[k] = a[++i] + b[j];
        else
            c[k] = a[i] + b[++j];
    }
    return c;
}

#line 2 "src/convolution/min_plus_convolution_convex_convex.hpp"
#include <cassert>
#include <vector>

template <typename T>
std::vector<T> min_plus_convolution_convex_convex(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]);
    for (int i = 0; i + 2 < m; i++) assert(b[i + 1] - b[i] <= b[i + 2] - b[i + 1]);
    std::vector<T> c(n + m - 1);
    c[0] = a[0] + b[0];
    for (int i = 0, j = 0, k = 1; k < n + m - 1; k++) {
        if (j == m - 1 or (i < n - 1 and a[i + 1] + b[j] < a[i] + b[j + 1]))
            c[k] = a[++i] + b[j];
        else
            c[k] = a[i] + b[++j];
    }
    return c;
}

Back to top page