Convex Min-Plus Convolution
(convolution/convex_min_plus_convolution.hpp)

• View this file on GitHub
• Last update: 2024-04-25 15:52:43+09:00
• Include: #include "convolution/convex_min_plus_convolution.hpp"

Description

数列 $a$ と上に凸な数列 $b$ の min-plus convolution $c_i=\min_j {a_j + b_{i-j}}$ を求める．

• vector<T> convex_min_plus_convolution(vector<T> a, vector<T> b)
  • 数列 $a$ と上に凸な数列 $b$ の min-plus convolution を求める
  • 時間計算量: $O((n + m) \log (n+m))$
• vector<T> concave_max_plus_convolution(vector<T> a, vector<T> b)
  • 数列 $a$ と下に凸な数列 $b$ の max-plus convolution を求める
  • 時間計算量: $O((n + m) \log (n+m))$

Reference

• [Tutorial] Knapsack, Subset Sum and the (max,+) Convolution

Depends on

• Monotone Minima (dp/monotone_minima.hpp)

Verified with

• test/yosupo/min_plus_convolution_convex_arbitrary.test.cpp

Code

#pragma once
#include <limits>
#include <vector>
#include "../dp/monotone_minima.hpp"

// b is convex
template <typename T>
std::vector<T> convex_min_plus_convolution(const std::vector<T>& a,
                                           const std::vector<T>& b) {
    int len = a.size() + b.size() - 1;

    auto f = [&](int i, int j) {
        if (i - j < 0 || (int)b.size() <= i - j)
            return std::numeric_limits<T>::max();
        return a[j] + b[i - j];
    };

    auto idx = monotone_minima(len, a.size(), f);
    std::vector<T> res(len);
    for (int i = 0; i < len; ++i) res[i] = f(i, idx[i]);
    return res;
}

// b is concave
template <typename T>
std::vector<T> concave_max_plus_convolution(std::vector<T> a,
                                            std::vector<T> b) {
    for (auto& x : a) x = -x;
    for (auto& x : b) x = -x;
    auto c = convex_min_plus_convolution(a, b);
    for (auto& x : c) x = -x;
    return c;
}

#line 2 "convolution/convex_min_plus_convolution.hpp"
#include <limits>
#include <vector>
#line 3 "dp/monotone_minima.hpp"

template <typename F>
std::vector<int> monotone_minima(int n, int m, const F& f) {
    std::vector<int> idx(n, -1);

    auto calc = [&](const auto& calc, int l, int r, int optl,
                    int optr) -> void {
        if (l > r) return;
        int m = std::midpoint(l, r);
        auto mi = f(m, optl);
        idx[m] = optl;
        for (int i = optl + 1; i <= optr; ++i) {
            auto v = f(m, i);
            if (mi > v) {
                mi = v;
                idx[m] = i;
            }
        }
        calc(calc, l, m - 1, optl, idx[m]);
        calc(calc, m + 1, r, idx[m], optr);
    };

    calc(calc, 0, n - 1, 0, m - 1);
    return idx;
}
#line 5 "convolution/convex_min_plus_convolution.hpp"

// b is convex
template <typename T>
std::vector<T> convex_min_plus_convolution(const std::vector<T>& a,
                                           const std::vector<T>& b) {
    int len = a.size() + b.size() - 1;

    auto f = [&](int i, int j) {
        if (i - j < 0 || (int)b.size() <= i - j)
            return std::numeric_limits<T>::max();
        return a[j] + b[i - j];
    };

    auto idx = monotone_minima(len, a.size(), f);
    std::vector<T> res(len);
    for (int i = 0; i < len; ++i) res[i] = f(i, idx[i]);
    return res;
}

// b is concave
template <typename T>
std::vector<T> concave_max_plus_convolution(std::vector<T> a,
                                            std::vector<T> b) {
    for (auto& x : a) x = -x;
    for (auto& x : b) x = -x;
    auto c = convex_min_plus_convolution(a, b);
    for (auto& x : c) x = -x;
    return c;
}

Back to top page