下に凸な数列同士の (min, +) convolution

より制約を弱くして一方のみが下に凸だとした場合も SMAWK Algorithm を使えば畳み込む数列の長さの和に対して線形時間で求まるんですが，両方ともが下に凸という制約を課した場合はかなり簡単に，かつ定数倍もかなり軽いアルゴリズムで求まることが分かったのでこの記事を書きました．

問題

長さ $N$ の数列 $A=(A _ 0,\ldots,A _ {N-1})$ と長さ $M$ の数列 $B=(B _ 0,\ldots, B _ {M-1})$ が与えられます．このとき，すべての $0\leq k\leq N + M - 2$ に対して

$\displaystyle C _ k = \min _ {i + j = k} A _ i + B _ j$

を求めてください．ただし， $A,B$ はともに下に凸であるとします．つまり，次の 2 つの条件を満たします．

条件:

全ての $1\leq i\leq N-2$ に対して $A _ i - A _ {i - 1} \leq A _ {i + 1} - A _ i$
全ての $1\leq j\leq M-2$ に対して $B _ j - B _ {j - 1} \leq B _ {j + 1} - B _ j$

解法

各 $k$ に対して， $i + j = k$ の下で $A _ i + B _ j$ を最小化する $i, j$ をそれぞれ $i _ k, j _ k$ と表す．ただし，そのような $i, j$ の組が複数ある場合は，適当に一つだけ選ぶことにする．

まず， $k=0$ の場合を考える．このときは，明らかに $i _ k = j _ k = 0$ である．

続いて， $k\gt 0$ の場合を考える．このとき，実は $(i _ k, j _ k) = (i _ {k - 1}, j _ {k - 1} + 1)$ または $(i _ k, j _ k) = (i _ {k - 1} + 1, j _ {k - 1})$ の 2 通りを試すだけでよい．これは，以下のような場合分けから従う．

$i \geq i _ {k - 1} + 1$ のとき

$\displaystyle \begin{aligned} A _ i + B _ {k - i} &= (A _ {i - 1} + B _ {k - i}) + (A _ i - A _ {i - 1}) \\ &\geq (A _ {i _ {k - 1}} + B _ {j _ {k - 1}}) + (A _ {i _ {k - 1} + 1} - A _ {i _ {k - 1}}) \\ &=A_{i_{k-1}+1}+B_{j_{k-1}} \end{aligned}$

$j \geq j _ {k - 1} + 1$ のとき

$\displaystyle \begin{aligned} A _ {k - j} + B _ j &= (A _ {k - j} + B _ {j - 1}) + (B _ j - B _ {j - 1}) \\ &\geq (A _ {i _ {k - 1}} + B _ {j _ {k - 1}}) + (B _ {j _ {k - 1} + 1} - B _ {j _ {k - 1}}) \\ &=A_{i_{k-1}}+B_{j_{k-1} + 1} \end{aligned}$

この事実を用いることで， $k=0,\ldots,N+M-2$ に対して $C _ k$ を $\Theta (N + M)$ 時間で求めることが出来る．

実装

std::vector<int> convolve(const std::vector<int> &a, const std::vector<int> &b) {
    constexpr int INF = std::numeric_limits<int>::max();
    int n = a.size();
    int m = b.size();
    if (n == 0 or m == 0) return {};
    std::vector<int> c(n + m - 1);
    c[0] = a[0] + b[0];
    int i = 0, j = 0;
    for (int k = 1; k <= n + m - 2; ++k) {
        int x = i + 1 == n ? INF : a[i + 1] + b[j];
        int y = j + 1 == m ? INF : a[i] + b[j + 1];
        if (x <= y) {
            c[k] = x;
            ++i;
        } else {
            c[k] = y;
            ++j;
        }
    }
    return c;
}

おまけ (片方のみが下に凸な場合)

以下， $A$ は任意の数列， $B$ は下に凸な数列としても一般性を失いません (逆なら swap すればよいので)．

$(M+N-1) \times N$ 行列 $P$ を次の図のように構築します．ただし， $P$ を陽に持った時点で計算量が $O( (N+M) M)$ となってしまうので，陰に持ちます (つまり，必要になった時に計算する)．

f:id:suisen_kyopro:20210527201819p:plain

このとき，結論から言えば， $P$ は totally monotone であることが示せます．従って，SMAWK Algorithm を用いることですべての $k$ に対する $\underset{i}{\arg \min}\, P _ {k, i}$ を $\Theta(N + M)$ で求めることができ，同時に $C _ k$ も求まります．SMAWK Algorithm に関しては，参考文献 [1] が分かりやすいので，詳細は省かせて頂きます (不等号の誤植があった気はしますが)．

SMAWK Algorithm の説明を省いた代わりに，ここでは $P$ が totally monotone であることを確認しておきましょう．これは，任意の $2\times 2$ 部分行列が monotone であることが言えればよいです．

$\displaystyle \begin{pmatrix} a & b\\ c & d \end{pmatrix}$

ここで，上のような $2\times 2$ 行列に対して，次のいずれかを満たす場合に monotone であるといいます．

$c\gt d$
$c=d$ かつ $a\leq b$
$c\lt d$ かつ $a\lt b$

つまり， $0\leq k _ 1\lt k _ 2\lt N + M - 1,\ 0\leq i _ 1\lt i _ 2\lt N$ を満たす $k _ 1, k _ 2, i _ 1, i _ 2$ であって，部分行列 $\displaystyle \begin{pmatrix} P _ {i _ 1, k _ 1}\;\, P _ {i _ 2, k _ 1} \\ P _ {i _ 1, k _ 2}\;\, P _ {i _ 2, k _ 2} \end{pmatrix}$ に関して

$P _ {i _ 1, k _ 2}=P _ {i _ 2, k _ 2}$ かつ $P _ {i _ 1, k _ 1}\gt P _ {i _ 2, k _ 1}$
$P _ {i _ 1, k _ 2}\lt P _ {i _ 2, k _ 2}$ かつ $P _ {i _ 1, k _ 1}\geq P _ {i _ 2, k _ 1}$

となるようなものが存在しないことを言えればよいです．まず， $\infty$ に対して適切な値を入れておくことで， $\infty$ を含むような $2\times 2$ 部分行列を monotone にできます ¹．従って，以下では部分行列が $\infty$ を含まない場合 ( $B$ が配列外参照を起こさない場合) を考えます．

$B$ が配列外参照を起こさないという仮定の下では，部分行列は次のように表すことが出来ます．

$\displaystyle \begin{pmatrix} P _ {i _ 1, k _ 1}& P _ {i _ 2, k _ 1} \\ P _ {i _ 1, k _ 2}& P _ {i _ 2, k _ 2} \end{pmatrix}= \begin{pmatrix} A _ {i _ 1} + B _ {k _ 1 - i _ 1} & A _ {i _ 2} + B _ {k _ 1 - i _ 2} \\ A _ {i _ 1} + B _ {k _ 2 - i _ 1} & A _ {i _ 2} + B _ {k _ 2 - i _ 2} \end{pmatrix}$

では，以下のいずれかが成立するという仮定を置いて，矛盾を導きます．

$P _ {i _ 1, k _ 2}=P _ {i _ 2, k _ 2}$ かつ $P _ {i _ 1, k _ 1}\gt P _ {i _ 2, k _ 1}$
$P _ {i _ 1, k _ 2}\lt P _ {i _ 2, k _ 2}$ かつ $P _ {i _ 1, k _ 1}\geq P _ {i _ 2, k _ 1}$

方針としては， $i _ 1\lt i _ 2,\ k _ 1\lt k _ 2$ に注意しながら， $B$ が下に凸であるという性質を活かせるように式変形を頑張るだけです．

$\displaystyle \begin{aligned} & \begin{cases} P _ {i _ 1, k _ 1}\gt P _ {i _ 2, k _ 1}\\ P _ {i _ 1, k _ 2}=P _ {i _ 2, k _ 2} \end{cases}\quad \text{or}\quad \begin{cases} P _ {i _ 1, k _ 1}\geq P _ {i _ 2, k _ 1}\\ P _ {i _ 1, k _ 2}\lt P _ {i _ 2, k _ 2} \end{cases} \\ \Rightarrow & \begin{cases} A _ {i _ 1} + B _ {k _ 2 - i _ 1}\gt A _ {i _ 2} + B _ {k _ 2 - i _ 2}\\ A _ {i _ 1} + B _ {k _ 1 - i _ 1}\leq A _ {i _ 2} + B _ {k _ 1 - i _ 2} \end{cases}\quad \text{or}\quad \begin{cases} A _ {i _ 1} + B _ {k _ 2 - i _ 1}\geq A _ {i _ 2} + B _ {k _ 2 - i _ 2}\\ A _ {i _ 1} + B _ {k _ 1 - i _ 1}\lt A _ {i _ 2} + B _ {k _ 1 - i _ 2} \end{cases} \\ \Rightarrow & A _ {i _ 1} + B _ {k _ 2 - i _ 1} - B _ {k _ 2 - i _ 2} \lt A _ {i _ 1} + B _ {k _ 1 - i _ 1} - B _ {k _ 1 - i _ 2} \\ \Rightarrow & B _ {k _ 2 - i _ 1} - B _ {k _ 2 - i _ 2}\lt B _ {k _ 1 - i _ 1} - B _ {k _ 1 - i _ 2} \\ \Rightarrow & \begin{cases} B _ {k _ 2 - i _ 1} - B _ {k _ 2 - i _ 2}\lt B _ {k _ 1 - i _ 1} - B _ {k _ 1 - i _ 2} \\ B _ {k _ 2 - i _ 1} - B _ {k _ 1 - i _ 1}\lt B _ {k _ 2 - i _ 2} - B _ {k _ 1 - i _ 2} \\ \end{cases} \\ \Rightarrow & \begin{cases} \displaystyle \sum _ {j = k _ 2 - i _ 2} ^ {k _ 2 - i _ 1 - 1} B _ {j + 1} - B _ {j} \lt \sum _ {j = k _ 1 - i _ 2} ^ {k _ 1 - i _ 1 - 1} B _ {j + 1} - B _ {j} \\ \displaystyle \sum _ {j = k _ 1 - i _ 1} ^ {k _ 2 - i _ 1 - 1} B _ {j + 1} - B _ {j} \lt \sum _ {j = k _ 1 - i _ 2} ^ {k _ 2 - i _ 2 - 1} B _ {j + 1} - B _ {j} \\ \end{cases} \\ \Rightarrow & \begin{cases} (i _ 2 - i _ 1)(B _ {k _ 2 - i _ 2 + 1} - B _ {k _ 2 - i _ 2}) \lt (i _ 2 - i _ 1)(B _ {k _ 1 - i _ 1 + 1} - B _ {k _ 1 - i _ 1})\\ \displaystyle (k _ 2 - k _ 1)(B _ {k _ 1 - i _ 1 + 1} - B _ {k _ 1 - i _ 1}) \lt (k _ 2 - k _ 1)(B _ {k _ 2 - i _ 2 + 1} - B _ {k _ 2 - i _ 2}) \end{cases} \\ \Rightarrow & \begin{cases} B _ {k _ 2 - i _ 2 + 1} - B _ {k _ 2 - i _ 2} \lt B _ {k _ 1 - i _ 1 + 1} - B _ {k _ 1 - i _ 1}\\ \displaystyle B _ {k _ 1 - i _ 1 + 1} - B _ {k _ 1 - i _ 1} \lt B _ {k _ 2 - i _ 2 + 1} - B _ {k _ 2 - i _ 2} \end{cases} \\ \end{aligned} \\$