Day 044-Q3 — Min-Plus畳み込み（凸列のmonotone minima）

2026-05-28 赤色 Master / Phase 8+ ★★★★★★★★★ Monge性 + 分割統治 / SMAWK

問題

長さ $N$ の配列 $A$ と長さ $M$ の配列 $B$ について、長さ $N+M-1$ の配列 $C$ を求めよ。

$$ C_k = \min_{i + j = k} (A_i + B_j) \quad (0 \le k \le N+M-2) $$

ただし $B$ は凸列（差分 $B_{j+1}-B_j$ が単調非減少）である。

制約

$1 \le N, M \le 5 \times 10^5$
$0 \le A_i, B_j \le 10^9$
$B$ は凸
時間制限: 3sec

入出力例

入力例 1

3 3
3 1 4
0 2 6

出力例 1

3 1 4 3 10

概念図: Monge行列の argmin 単調性

行列 D[k][i]=A_i+B_{k-i} は totally monotone → 各行 argmin が単調増加 i=0 i=1 i=2 i=3 i=4 k=0 k=1 k=2 k=3 min min min min monotone minima 中央行 k_mid の argmin = i* を線形探索 上半分 → i ≤ i* 下半分 → i ≥ i* → O((N+M) log) 一般のMin-Plusは O(NM)（subquadratic不可・SETH仮説）。片方の凸性で Monge 化 → 高速化できる。

ヒント（段階的開示）

ヒント1: 方向性
一般の Min-Plus 畳み込みは $O(NM)$ で FFT 的高速化は存在しない（SETH仮説下で真に subquadratic 不可）。だが片方が凸なら $O(N+M)$〜$O((N+M)\log)$ で解ける。
ヒント2: アプローチ
$B$ が凸のとき $D[k][i]=A_i+B_{k-i}$ は totally monotone（Monge）。各行の argmin が $k$ について単調増加するので SMAWK / monotone minima で全行最小を高速計算できる。
ヒント3: 誘導
実装が容易なのは monotone minima（分割統治最適化）。中央行の argmin を求めて範囲を二分し再帰。$O((N+M)\log(N+M))$。SMAWK なら対数因子を落として $O(N+M)$。

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    A = [int(data[idx + i]) for i in range(N)]; idx += N
    B = [int(data[idx + i]) for i in range(M)]; idx += M

    L = N + M - 1
    INF = float('inf')
    C = [INF] * L

    def cost(k, i):
        j = k - i
        if 0 <= j < M and 0 <= i < N:
            return A[i] + B[j]
        return INF

    sys.setrecursionlimit(1 << 20)
    def rec(klo, khi, ilo, ihi):
        if klo >= khi:
            return
        kmid = (klo + khi) >> 1
        best_i = -1; best_v = INF
        lo = max(ilo, kmid - (M - 1))
        hi = min(ihi, kmid, N - 1)
        for i in range(lo, hi + 1):
            v = cost(kmid, i)
            if v < best_v:
                best_v = v; best_i = i
        C[kmid] = best_v
        if best_i == -1:
            best_i = ilo
        rec(klo, kmid, ilo, best_i)
        rec(kmid + 1, khi, best_i, ihi)

    rec(0, L, 0, N - 1)
    sys.stdout.write(' '.join(map(str, C)) + '\n')

solve()

Step-by-Step 解説

1Min-Plus の難しさ
通常版は $O(NM)$。FFTは $(+,\times)$ 半環でしか効かず $(\min,+)$ では使えない。一般高速化は条件付き下界で否定的。
2凸性 → Monge性
$B$ が凸なら $D[k][i]=A_i+B_{k-i}$ は totally monotone。各行の argmin が $k$ について単調非減少。
3monotone minima
中央行 $k_{mid}$ の最適列 $i^*$ を線形探索。上半分は $\le i^*$、下半分は $\ge i^*$ に絞り再帰。$O((N+M)\log)$。
4境界処理
$j=k-i \in [0,M)$ かつ $i \in [0,N)$ のみ有効。探索範囲 lo/hi をこれで clamp。
5SMAWK で $O(N+M)$
reduce + interpolate により対数因子を落とせる。実装は複雑だが理論最速。

計算量

素朴: $O(NM)$
monotone minima: $O((N+M)\log(N+M))$
SMAWK: $O(N+M)$
空間: $O(N+M)$

よくあるミス

ミス原因正しい書き方
一般Min-Plusに分割統治適用凸性がないとMongeでない片方の凸性を必ず確認
argmin単調性の向きを誤るmin/max で逆minなら凸B、maxなら凹B
探索範囲未clampj が範囲外で誤最小lo=max(ilo,k-(M-1))
best_i=-1の処理漏れ有効解なしの行ilo を引き継ぐ

次のステップ

  • 発展問題: 両方が凸 → Minkowski和で $O(N+M)$（差分列マージソート）
  • 類題: スライド最小値DP、Convex Hull Trick との関係
  • 応用: ナップサックの分割統治、コスト分割最適化

自己評価