haar_lib/math/convolution/
min_plus_conv_convex.rs

1//! 和の最小値で畳み込み
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary>
5use crate::algo::monotone_minima::*;
6
7/// $c_k = \min_{i + j = k} (a_i + b_j)$を満たす$c$を求める。
8///
9/// # Requirements
10/// `a`は下に凸な列である。
11///
12/// # Return
13/// `c.len` = `a.len() + b.len() - 1`
14pub fn min_plus_conv_convex(a: Vec<i64>, b: Vec<i64>) -> Vec<i64> {
15    assert!(!a.is_empty());
16    assert!(!b.is_empty());
17    let n = a.len();
18    let m = b.len();
19
20    if n >= 2 {
21        for i in 0..n - 2 {
22            assert!(2 * a[i + 1] <= a[i + 2] + a[i], "`a`が下に凸ではない。");
23        }
24    }
25
26    let f = |i, j| {
27        if i < j || i >= n + j {
28            i64::MAX
29        } else {
30            a[i - j] + b[j]
31        }
32    };
33    monotone_minima(n + m - 1, m, f)
34        .into_iter()
35        .map(|(_, c)| c)
36        .collect()
37}
38
39#[cfg(test)]
40mod tests {
41    use crate::{chmin, iter::collect::CollectVec};
42
43    use super::*;
44
45    use rand::Rng;
46
47    #[test]
48    fn test() {
49        let mut rng = rand::thread_rng();
50
51        for _ in 0..10 {
52            let n = rng.gen_range(100..=500);
53            let m = rng.gen_range(100..=500);
54
55            let a = {
56                // let argmin = rng.gen_range(0..n);
57
58                let mut a = vec![0; n];
59
60                let mut d = -500;
61
62                a[0] = rng.gen_range(-1000..=1000);
63
64                for i in 1..n {
65                    let dd = rng.gen_range(0..10);
66                    d += dd;
67                    a[i] = a[i - 1] + d;
68                }
69
70                a
71            };
72            let b = std::iter::repeat_with(|| rng.gen_range(-1000..=1000))
73                .take(m)
74                .collect_vec();
75
76            let mut ans = vec![i64::MAX; n + m - 1];
77            for i in 0..n {
78                for j in 0..m {
79                    chmin!(ans[i + j], a[i] + b[j]);
80                }
81            }
82
83            assert_eq!(ans, min_plus_conv_convex(a, b));
84        }
85    }
86}
haar_lib/math/convolution/min_plus_conv_convex.rs

haar_lib/math/convolution/
min_plus_conv_convex.rs
