AtCoder Beginner Contest 394 D

https://atcoder.jp/contests/abc394/tasks/abc394_d

隣合うの2文字がマッチしたらそれらを削除してつなぎ合わせればよいので、リスト構造を使えばよいです。それをVecで作ればRustでも簡単に書けます。

// Colorful Bracket Sequence
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn YesNo(b: bool) -> String {
    return if b { "Yes" } else { "No" }.to_string()
}


//////////////////// List ////////////////////

struct List {
    v: Vec<usize>
}

impl List {
    fn prev(&self, p: usize) -> usize {
        self.v[p]
    }
    
    fn next(&self, p: usize) -> usize {
        self.v[p+2]
    }
    
    fn char(&self, p: usize) -> usize {
        self.v[p+1]
    }
    
    fn set_prev(&mut self, p: usize, q: usize) {
        self.v[p] = q
    }
    
    fn set_next(&mut self, p: usize, q: usize) {
        self.v[p+2] = q
    }
    
    fn remove(&mut self, p: usize) {
        let prev_pos = self.prev(p);
        let next_pos = self.next(p);
        if prev_pos != usize::MAX {
            self.set_next(prev_pos, next_pos)
        }
        if next_pos != usize::MAX {
            self.set_prev(next_pos, prev_pos)
        }
    }
    
    fn create(v: &Vec<usize>) -> List {
        let L = v.len();
        let mut w: Vec<usize> = vec![usize::MAX; L*3];
        for i in 1..L {
            w[i*3] = (i-1) * 3
        }
        for i in 0..L {
            w[i*3+1] = v[i]
        }
        for i in 0..L-1 {
            w[i*3+2] = (i+1) * 3
        }
        List { v: w }
    }
}


//////////////////// process ////////////////////

fn is_matched(c1: usize, c2: usize) -> bool {
    c1 % 2 == 0 && c2 == c1 + 1
}

fn F(S: String) -> bool {
    let L = S.len();
    if L % 2 == 1 {
        return false
    }
    
    let v: Vec<usize> = S.chars().map(|c| match c {
                                            '(' => 0,
                                            ')' => 1,
                                            '[' => 2,
                                            ']' => 3,
                                            '<' => 4,
                                            _   => 5 }).collect();
    
    let mut l = List::create(&v);
    let mut p: usize = 0;
    loop {
        let next_p = l.next(p);
        if next_p == usize::MAX {
            break
        }
        let next_next_p = l.next(next_p);
        if is_matched(l.char(p), l.char(next_p)) {
            let prev_p = l.prev(p);
            l.remove(p);
            l.remove(next_p);
            if prev_p != usize::MAX {
                p = prev_p;
                if next_p == usize::MAX {
                    return false
                }
            }
            else if next_next_p == usize::MAX {
                return true
            }
            else {
                p = next_next_p;
                l.set_prev(p, usize::MAX)
            }
        }
        else {
            if next_next_p == usize::MAX {
                return false
            }
            else {
                p = next_p
            }
        }
    }
    
    false
}

fn main() {
    let S: String = read();
    println!("{}", YesNo(F(S)))
}