Min Plus Convolution
(convolution/min_plus_convolution.hpp)

• View this file on GitHub
• Last update: 2023-11-08 11:18:30+09:00
• Include: #include "convolution/min_plus_convolution.hpp"

説明

長さ$N$ の凸な整数列 $a$ と 長さ $M$ の整数列 $b$ について、 $c_k = \min_{i + j = k} (a_i + b_j)$ となる長さ $N+M-1$ の整数列を求める。 $O(N + M\log N)$

ここで、凸な数列とは $0 \leq i < N-2$ に対して $a_{i + 1} - a_i \leq a_{i + 2} - a_{i + 1}$ が成り立つことをいう。

Depends on

• Monotone Minima (algorithm/monotone_minima.hpp)

Verified with

• test/convolution/Min_Plus_Convolution_Convex_and_Arbitary.test.cpp

Code

#pragma once

#include <cassert>
#include <limits>
#include <vector>

#include "../algorithm/monotone_minima.hpp"

namespace ebi {

template <class T>
std::vector<T> min_plus_convolution_convex_and_arbitary(
    const std::vector<T> &a, const std::vector<T> &b) {
    int n = (int)a.size();
    int m = (int)b.size();
    for (int i = 0; i < n - 2; i++) {
        assert(a[i + 1] - a[i] <= a[i + 2] - a[i + 1]);
    }
    auto f = [&](int i, int j) -> T {
        if (i - j < 0 || i - j >= n) return std::numeric_limits<T>::max();
        return a[i - j] + b[j];
    };
    auto [argmin, min_val] = monotone_minima(n + m - 1, m, f);
    return min_val;
}

}  // namespace ebi

#line 2 "convolution/min_plus_convolution.hpp"

#include <cassert>
#include <limits>
#include <vector>

#line 2 "algorithm/monotone_minima.hpp"

#include <functional>
#include <utility>
#line 6 "algorithm/monotone_minima.hpp"

namespace ebi {

template <class F,
          class T = decltype(std::declval<F>()(std::declval<int>(),
                                               std::declval<int>())),
          class Compare = std::less<T>>
std::pair<std::vector<int>, std::vector<T>> monotone_minima(
    int n, int m, F f, const Compare &compare = Compare()) {
    std::vector<int> argmin(n);
    std::vector<T> min_val(n);
    auto dfs = [&](auto &&self, int top, int bottom, int left,
                   int right) -> void {
        if (top > bottom) return;
        int mid = (top + bottom) >> 1;
        argmin[mid] = left;
        min_val[mid] = f(mid, left);
        for (int i = left + 1; i <= right; i++) {
            T val = f(mid, i);
            if (min_val[mid] == val || compare(val, min_val[mid])) {
                argmin[mid] = i;
                min_val[mid] = val;
            }
        }
        self(self, top, mid - 1, left, argmin[mid]);
        self(self, mid + 1, bottom, argmin[mid], right);
    };
    dfs(dfs, 0, n - 1, 0, m - 1);
    return {argmin, min_val};
}

template <class T, class F, class Compare = std::less<T>>
std::pair<std::vector<int>, std::vector<T>> slide_monotone_minima(
    int n, int m, F f, const Compare &compare = Compare()) {
    std::vector<int> argmin(n);
    std::vector<T> min_val(n);
    auto dfs = [&](auto &&self, int top, int bottom, int left, int right,
                   int depth) -> void {
        if (top > bottom) return;
        int mid = (top + bottom) >> 1;
        argmin[mid] = left;
        min_val[mid] = f(mid, left, depth);
        for (int i = left + 1; i <= right; i++) {
            T val = f(mid, i, depth);
            if (min_val[mid] == val || compare(val, min_val[mid])) {
                argmin[mid] = i;
                min_val[mid] = val;
            }
        }
        self(self, top, mid - 1, left, argmin[mid], depth + 1);
        self(self, mid + 1, bottom, argmin[mid], right, depth + 1);
    };
    dfs(dfs, 0, n - 1, 0, m - 1, 0);
    return {argmin, min_val};
}

}  // namespace ebi
#line 8 "convolution/min_plus_convolution.hpp"

namespace ebi {

template <class T>
std::vector<T> min_plus_convolution_convex_and_arbitary(
    const std::vector<T> &a, const std::vector<T> &b) {
    int n = (int)a.size();
    int m = (int)b.size();
    for (int i = 0; i < n - 2; i++) {
        assert(a[i + 1] - a[i] <= a[i + 2] - a[i + 1]);
    }
    auto f = [&](int i, int j) -> T {
        if (i - j < 0 || i - j >= n) return std::numeric_limits<T>::max();
        return a[i - j] + b[j];
    };
    auto [argmin, min_val] = monotone_minima(n + m - 1, m, f);
    return min_val;
}

}  // namespace ebi

Back to top page