Min Plus Convolution (Convex and Arbitary) (dp/min-plus-convolution-convex-arbitary.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-08-23 08:59:58+00:00
• Include: #include "dp/min-plus-convolution-convex-arbitary.hpp"

凸数列と任意の数列の min-plus 畳み込みを SMAWK により線形時間で計算する。

min_plus_convolution_convex_arbitary

template <typename T>
vector<T> min_plus_convolution_convex_arbitary(const vector<T>& a,
                                               const vector<T>& b)

$a$ を凸数列、$b$ を任意の数列として、各 $k$ に対する $\min_{i+j=k}(a_i+b_j)$ を並べた配列を返す。どちらかが空なら空配列を返す。

テンプレート引数

• T: 加算と < による比較が可能な要素型

引数

• a: 隣接差分が広義単調増加する凸数列
• b: 任意の数列

戻り値

両方の入力が空でない場合、長さ $\lvert a\rvert + \lvert b\rvert - 1$ の min-plus 畳み込みを返す。

前提条件

• a は凸数列である
• 配列長と要素の加算結果は、それぞれ int と T で表現できる

計算量

$N = \lvert a\rvert$, $M = \lvert b\rvert$ とする。

• 時間: $O(N + M)$
• 空間: $O(N + M)$

Depends on

• SMAWK (dp/smawk.hpp)

Verified with

• test/verify/yosupo-min-plus-convolution-convex-arbitrary.test.cpp

Code

#pragma once

#include <vector>

#include "smawk.hpp"

template <typename T>
std::vector<T> min_plus_convolution_convex_arbitary(const std::vector<T>& a,
                                                    const std::vector<T>& b) {
  if (a.empty() || b.empty()) return {};
  int H = static_cast<int>(a.size());
  int W = static_cast<int>(b.size());
  const auto c = smawk(H + W - 1, W, [&](int i, int j, int k) {
    if (i < k) return false;
    if (i - j >= H) return true;
    return b[k] + a[i - k] < b[j] + a[i - j];
  });
  std::vector<T> ret;
  ret.reserve(H + W - 1);
  for (int i = 0; i < H + W - 1; ++i) {
    ret.emplace_back(b[c[i]] + a[i - c[i]]);
  }
  return ret;
}

#line 2 "dp/min-plus-convolution-convex-arbitary.hpp"

#include <vector>

#line 2 "dp/smawk.hpp"

#include <algorithm>
#include <numeric>
#line 6 "dp/smawk.hpp"

template <typename F>
std::vector<int> smawk(int H, int W, F comp) {
  std::vector<int> ret(H, -1);
  if (H == 0 || W == 0) return ret;

  auto dfs = [&](auto&& self, const std::vector<int>& rows,
                 const std::vector<int>& cols) -> void {
    if (rows.empty()) return;
    std::vector<int> reduced;
    reduced.reserve(std::min(rows.size(), cols.size()));
    for (int c : cols) {
      while (!reduced.empty()) {
        int r = rows[reduced.size() - 1];
        int old_c = reduced.back();
        if (comp(r, old_c, c)) {
          reduced.pop_back();
        } else {
          break;
        }
      }
      if (reduced.size() < rows.size()) reduced.emplace_back(c);
    }

    std::vector<int> odd_rows;
    odd_rows.reserve(rows.size() / 2);
    for (int i = 1; i < static_cast<int>(rows.size()); i += 2) {
      odd_rows.emplace_back(rows[i]);
    }
    self(self, odd_rows, reduced);

    int left = 0;
    for (int i = 0; i < static_cast<int>(rows.size()); i += 2) {
      int right = static_cast<int>(reduced.size()) - 1;
      if (i + 1 < static_cast<int>(rows.size())) {
        right = left;
        while (reduced[right] != ret[rows[i + 1]]) ++right;
      }
      int best = left;
      for (int p = left + 1; p <= right; ++p) {
        if (comp(rows[i], reduced[best], reduced[p])) best = p;
      }
      ret[rows[i]] = reduced[best];
      left = right;
    }
  };

  std::vector<int> rows(H), cols(W);
  std::iota(rows.begin(), rows.end(), 0);
  std::iota(cols.begin(), cols.end(), 0);
  dfs(dfs, rows, cols);
  return ret;
}
#line 6 "dp/min-plus-convolution-convex-arbitary.hpp"

template <typename T>
std::vector<T> min_plus_convolution_convex_arbitary(const std::vector<T>& a,
                                                    const std::vector<T>& b) {
  if (a.empty() || b.empty()) return {};
  int H = static_cast<int>(a.size());
  int W = static_cast<int>(b.size());
  const auto c = smawk(H + W - 1, W, [&](int i, int j, int k) {
    if (i < k) return false;
    if (i - j >= H) return true;
    return b[k] + a[i - k] < b[j] + a[i - j];
  });
  std::vector<T> ret;
  ret.reserve(H + W - 1);
  for (int i = 0; i < H + W - 1; ++i) {
    ret.emplace_back(b[c[i]] + a[i - c[i]]);
  }
  return ret;
}

Back to top page