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)); }