atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ 凸性 min-plus 畳み込み 畳み込み 解説動画はこちらです． 1. 概要 $2$ つの整数列（または実数列）$A = (A _ 0, A _ 1, \ldots, A _ {N})$, $B = (B _ 0, B _ 1, \ldots, B _ {M})$ に対して， $C _ k = \min _ {i + j = k}(A _ i + B _ j)$ により定義される列 $C = (C _ 0, \ldots, C _ {N+M})$ を $A, B$ の min-plus 畳み込みといいます． $A, B$ のうち少なくとも一方に凸性がある場合には min-plus 畳み込みを高速に行えることが知られています． 本記事で… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Fmin_plus_convolution" title="凸数列の min-plus 畳み込み - AtCoderInfo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/158934417/1702097020779738 Hatena Blog https://hatena.blog 2026-04-10 14:12:01 rich https://info.atcoder.jp/entry/algorithm_lectures/min_plus_convolution 1.0 100%