haar_lib/algebra/
parenthesis.rs

1//! 括弧列
2//!
3//! # Problems
4//! - <https://atcoder.jp/contests/abc223/tasks/abc223_f>
5pub use crate::algebra::traits::*;
6use crate::impl_algebra;
7
8/// 括弧列
9#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
10pub struct ParenSeq {
11    /// 対応する`(`がない`)`の個数。
12    pub close: u64,
13    /// 対応する`)`がない`(`の個数。
14    pub open: u64,
15}
16
17impl ParenSeq {
18    /// 空の括弧列を返す。
19    pub fn empty() -> Self {
20        Self { close: 0, open: 0 }
21    }
22
23    /// 括弧列が正しい括弧列かを判定する。
24    pub fn is_correct(self) -> bool {
25        self.close == 0 && self.open == 0
26    }
27
28    /// 連続した`n`個の開いた括弧`(`からなる列。
29    pub fn open(n: u64) -> Self {
30        Self { close: 0, open: n }
31    }
32
33    /// 連続した`n`個の閉じた括弧`)`からなる列。
34    pub fn close(n: u64) -> Self {
35        Self { close: n, open: 0 }
36    }
37
38    /// 括弧列`self`の右に括弧列`right`を結合して、対応のとれた括弧対をすべて潰した括弧列を返す。
39    pub fn concat(self, right: Self) -> Self {
40        let Self { close: a, open: b } = self;
41        let Self { close: c, open: d } = right;
42
43        Self {
44            close: a + c.saturating_sub(b),
45            open: d + b.saturating_sub(c),
46        }
47    }
48}
49
50/// 括弧列の結合を演算とするモノイド
51#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
52pub struct Composition;
53
54impl_algebra!(Composition; set: ParenSeq; op: |_, a: ParenSeq, b| a.concat(b);
55              id: |_| ParenSeq::empty(); assoc;
56);
haar_lib/algebra/parenthesis.rs

haar_lib/algebra/
parenthesis.rs
