haar_lib/algo/
shakutori.rs

1//! 尺取り法
2//!
3//! # Problems
4//! - <https://atcoder.jp/contests/abc038/tasks/abc038_c>
5//! - <https://atcoder.jp/contests/arc022/tasks/arc022_2>
6//! - <https://atcoder.jp/contests/abc444/tasks/abc444_e>
7
8/// 尺取り法
9///
10/// * remove_left - `|l: usize| {尺取りの左端を縮めたときの操作}`
11/// * can_append_right - `|l: usize, r: usize| {l..r+1が条件を満たすかを判定}`
12/// * append_right - `|r: usize| {尺取りの右端を進めたときの操作}`
13pub fn shakutori(
14    n: usize,
15    mut remove_left: impl FnMut(usize),
16    can_append_right: impl Fn(usize, usize) -> bool,
17    mut append_right: impl FnMut(usize),
18    mut f: impl FnMut(usize, usize),
19) {
20    let mut right = 0;
21
22    for left in 0..n {
23        if right < left {
24            right = left;
25        }
26
27        while right < n {
28            if can_append_right(left, right) {
29                append_right(right);
30                right += 1;
31            } else {
32                break;
33            }
34        }
35
36        f(left, right);
37
38        if left < right {
39            remove_left(left);
40        }
41    }
42}
haar_lib/algo/shakutori.rs

haar_lib/algo/
shakutori.rs
