Min-Plus Convolution

第1引数が凸列である場合のmin-plus convolutionを計算します。

長さnの列convexと長さmの列arbitraryに対し、 長さn + m - 1の列resultを返します。

各indexkについて、範囲内のiを用いて次を計算します。

result[k] = min(convex[k - i] + arbitrary[i])

一般形

minPlusConvolutionConvexArbitrary(
  convex: openArray[int64],
  arbitrary: openArray[int64],
): seq[int64]

引数

• convex: openArray[int64]: 隣接差分が広義単調増加する凸列です。
• arbitrary: openArray[int64]: 任意のint64列です。

両方の入力列は変更されません。

返り値

• seq[int64]: min-plus convolutionの結果を新しい列として返します。

どちらかの入力が空の場合は空列を返します。

例外

convexが凸列でない場合はValueErrorを送出します。

制約

• convex[i] + arbitrary[j]がint64の範囲に収まる
• convexの隣接差分が広義単調増加する

計算量

n = convex.len、m = arbitrary.lenとします。

現在のdivide-and-conquer monotone optimization実装では、

• 時間: O((n + m) log(n + m))
• 追加メモリ: O(n + m)

です。

使用例

import atcoder/extra/math/min_plus_convolutionlet convex =  @[0'i64, 1, 4]let arbitrary =  @[3'i64, 0]doAssert minPlusConvolutionConvexArbitrary(  convex,  arbitrary,) == @[3'i64, 0, 1, 4]

import方法

import atcoder/extra/math/min_plus_convolution

主なAPI

• minPlusConvolutionConvexArbitrary