Take ABC 2 の解説

よくある真ん中を固定して考える問題。

あるindex'B'を選んだとき、その左側にあるAとその右側にあるCを選ぶことでそのi, j, kを取り除くことができる。

この際、左側のAはどこでも取り除いて良いが、右側はBより右側にあり、かつindexが小さいCから選ぶ必要がある。

これは、のちに選べるCをできる限り残しておきたいお気持ち。

rustはBTreeSetでCのindexを管理しておくことで、あるindexよりも上の最小の値というものが簡単O(log n)で求められるので便利。

fn main() {
    input! {
        s: Chars
    }
    if s.len() <= 2 {
        return println!("0");
    }
    let mut a = BTreeSet::new();
    let mut c = BTreeSet::new();
    if s[0] == 'A' {
        a.insert(0);
    }
    for i in 2..s.len() {
        if s[i] == 'C' {
            c.insert(i);
        }
    }
    
    let mut ans = 0;
    for b in 1..s.len() - 1 {
        if s[b] == 'B' && a.len() > 0 && c.len() > 0 {
            a.pop_last().unwrap();
            let &nex = c.range(b + 1..).next().unwrap();
            c.remove(&nex);
            ans += 1usize;
        }
        if s[b] == 'A' {
            a.insert(b);
        }
        if s[b + 1] == 'C' {
            c.remove(&(b + 1));
        }
    }
    println!("{}", ans);
}