AtCoder Beginner Contest 312 D

https://atcoder.jp/contests/abc312/tasks/abc312_d

DPですね。'('が出てきたら右に進んで、')'が出てきたら上に進みます。'?'ならどちらにも進めます。

// Count Bracket Sequences
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// constants ////////////////////

const D: u64 = 998244353;


//////////////////// 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()
}


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

fn f(S: String) -> u64 {
    let cs = String::from("()?");
    let T: String = S.chars().filter(|&c| cs.contains(c)).collect();
    let L = T.len();
    if L % 2 != 0 {
        return 0
    }
    
    let N = L / 2;
    let mut table: Vec<Vec<u64>> = (0..N+1).map(|_| vec![0; N+1]).collect();
    table[0][0] = 1;
    for (i, c) in S.chars().enumerate() {
        let min_x = (i + 1) / 2;
        let max_x = min(N, i);
        for x in min_x..max_x+1 {
            let y = i - x;
            if c != ')' {
                if x + 1 <= N {
                    table[y][x+1] = (table[y][x+1] + table[y][x]) % D
                }
            }
            if c != '(' {
                if y + 1 <= x {
                    table[y+1][x] = (table[y+1][x] + table[y][x]) % D
                }
            }
        }
    }
    table[N][N]
}


//////////////////// main ////////////////////

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