min-plus 畳み込み (convex)
(convolution/min-plus-convex.hpp)

• View this file on GitHub
• Last update: 2025-10-10 17:35:46+09:00
• Include: #include "convolution/min-plus-convex.hpp"

二つの数列 $(a_0,\dots,a_{n-1}),(b_0,\dots,b_{m-1})$ から以下を満たす数列 $(c_0,\dots,c_{n+m-2})$ を計算する．

\[c_k=\min_{i+j=k}(a_i+b_j)\]

ただし $a$ は下に凸，すなわち $a_i-a_{i-1}\leq a_{i+1}-a_i$ を満たす必要がある．

• monotone minima を用いる場合 $O((n+m)\log(n+m))$ 時間．
• SMAWK を用いるか $b$ も凸な場合 $O(n+m)$ 時間．

monotone minima と SMAWK は実用上だと定数倍の問題で大差ないという話もある．

convex-arbitrary

$A_{i,j}=a_{i-j}+b_j$ として $(n+m-1)\times m$ 行列 $A$ を考える． ただし値が存在しない場所は $\infty$ で埋める．

ある $i$ および $k\lt l$ に対し $A_{i,k}\gt A_{i,l}$ であると仮定する． このとき任意の $j\gt i$ について

\[A_{j,k}-A_{j,l}=a_{j-k}-a_{j-l}+b_k-b_l\geq a_{i-k}-a_{i-l}+b_k-b_l=A_{i,k}-A_{i,l}\gt 0\]

より $A_{j,k}\gt A_{j,l}$ である．

従って $A$ は monotone であり，monotone minima や SMAWK によって列毎の argmin が列挙できる． argmin が求まれば $c$ も容易に計算できる．

convex-convex

上の議論をまとめれば $f(k)=\min\operatorname{arg\,min}{i}(a{k-i}+b_i)$ は $k$ について単調増加である．

$a,b$ を入れ替えても同じことがいえることから，$f(k+1)-f(k)\in{0,1}$ が得られる．

従って以下の流れで $c$ が求められる．

• $(i,j)=(0,0)$ から始めて，$i+j\leq n+m-2$ の間以下を繰り返す．
  • $c_{i+j}=a_i+b_j$ とする．
  • $a_{i+1}+b_{j} \lt a_{i}+b_{j+1}$ ならば $(i,j)\to(i+1,j)$，そうでないならば $(i,j)\to(i,j+1)$ へ遷移する．

Depends on

• monotone minima (algorithm/monotone-minima.hpp)

Verified with

• verify/convolution/LC_min_plus_convolution_convex_arbitrary.test.cpp
• verify/convolution/LC_min_plus_convolution_convex_convex.test.cpp

Code

#pragma once

#include "../algorithm/monotone-minima.hpp"

// a : 下に凸, b : 自由
template <class T>
vector<T> MinPlusConvolutionConvexArbitrary(const vector<T> &a, const vector<T> &b) {
  if (a.empty() || b.empty()) return {};
  int n = a.size(), m = b.size();
  auto argmin = MonotoneMinima(n + m - 1, m, [&](int i, int j, int k) {
    if (i < k) return true;
    if (i - j >= n) return false;
    return a[i - j] + b[j] <= a[i - k] + b[k];
  });
  vector<T> c(n + m - 1);
  for (int i = 0; i < n + m - 1; i++) {
    int j = argmin[i];
    c[i] = a[i - j] + b[j];
  }
  return c;
}

// a,b : 下に凸
template <class T>
vector<T> MinPlusConvolutionConvexConvex(const vector<T> &a, const vector<T> &b) {
  if (a.empty() || b.empty()) return {};
  int n = a.size(), m = b.size();
  vector<T> c(n + m - 1);
  c[0] = a[0] + b[0];
  for (int k = 0, i = 0; k < n + m - 2; k++) {
    int j = k - i;
    if (j == m - 1 || (i < n - 1 && a[i + 1] + b[j] < a[i] + b[j + 1])) {
      c[k + 1] = a[++i] + b[j];
    } else {
      c[k + 1] = a[i] + b[++j];
    }
  }
  return c;
}

/**
 * @brief min-plus 畳み込み (convex)
 * @docs docs/convolution/min-plus-convex.md
 */

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

#line 2 "algorithm/monotone-minima.hpp"

vector<int> MonotoneMinima(int n, int m, const function<bool(int, int, int)> &f) {
  vector<int> res(n);
  auto dfs = [&](auto rc, int il, int ir, int l, int r) -> void {
    if (il == ir) return;
    int i = (il + ir) / 2;
    int m = l;
    for (int k = l + 1; k < r; k++)
      if (!f(i, m, k)) m = k;
    res[i] = m;
    rc(rc, il, i, l, m + 1);
    rc(rc, i + 1, ir, m, r);
  };
  dfs(dfs, 0, n, 0, m);
  return res;
}

// m_i := argmin_j (A_{i,j}) が単調増加であるときに m_i を列挙する
template <class T>
vector<int> MonotoneMinima(int N, int M, const function<T(int, int)> &A) {
  const auto f = [&](int i, int j, int k) -> bool {
    return A(i, j) <= A(i, k);
  };
  return MonotoneMinima(N, M, f);
}

/**
 * @brief monotone minima
 * @docs docs/algorithm/monotone-minima.md
 */
#line 4 "convolution/min-plus-convex.hpp"

// a : 下に凸, b : 自由
template <class T>
vector<T> MinPlusConvolutionConvexArbitrary(const vector<T> &a, const vector<T> &b) {
  if (a.empty() || b.empty()) return {};
  int n = a.size(), m = b.size();
  auto argmin = MonotoneMinima(n + m - 1, m, [&](int i, int j, int k) {
    if (i < k) return true;
    if (i - j >= n) return false;
    return a[i - j] + b[j] <= a[i - k] + b[k];
  });
  vector<T> c(n + m - 1);
  for (int i = 0; i < n + m - 1; i++) {
    int j = argmin[i];
    c[i] = a[i - j] + b[j];
  }
  return c;
}

// a,b : 下に凸
template <class T>
vector<T> MinPlusConvolutionConvexConvex(const vector<T> &a, const vector<T> &b) {
  if (a.empty() || b.empty()) return {};
  int n = a.size(), m = b.size();
  vector<T> c(n + m - 1);
  c[0] = a[0] + b[0];
  for (int k = 0, i = 0; k < n + m - 2; k++) {
    int j = k - i;
    if (j == m - 1 || (i < n - 1 && a[i + 1] + b[j] < a[i] + b[j + 1])) {
      c[k + 1] = a[++i] + b[j];
    } else {
      c[k + 1] = a[i] + b[++j];
    }
  }
  return c;
}

/**
 * @brief min-plus 畳み込み (convex)
 * @docs docs/convolution/min-plus-convex.md
 */

Back to top page