AtCoder Beginner Contest 313 E

https://atcoder.jp/contests/abc313/tasks/abc313_e

1より大きい数字が2つ続くと明らかに終わらないので、1のブロックと1より大きい数字が交互に現れるという前提にします。また、最初に1より大きい数字が現れたとき、最初の数字は固定されるので、最初の数字を除いたときの回数に+1すればよいです。最後の文字が1より大きいときは、1回進めて、
(1のブロック)(1より大きい数字)...(1のブロック)
という形に正規化します。

正規化したら、
、として、Vecに、を格納します。そうすると、回後に

となります。これを繰り返すと最終的にを求められます。

// Duplicate
#![allow(non_snake_case)]


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

const D: i64 = 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 read_input() -> String {
    let _N: usize = read();
    let S = read();
    S
}

fn to_vec(S: String) -> Vec<i64> {
    let mut v: Vec<i64> = vec![];
    for c in S.chars() {
        let d = (c as i64) - ('0' as i64);
        let L = v.len();
        if d == 1 {
            if L == 0 {
                v.push(-1)
            }
            else if v[L-1] > 0 {
                v.push(-1)
            }
            else {
                v[L-1] -= 1
            }
        }
        else {
            if L == 0 {
                v.push(d)
            }
            else if v[L-1] > 0 {
                v.clear();
                break
            }
            else {
                v.push(d)
            }
        }
    }
    v
}

fn normalize(v: &mut Vec<i64>) -> i64 {
    if v.is_empty() {
        0
    }
    else if v[0] > 0 {
        v.remove(0);
        normalize(v) + 1
    }
    else {
        if *v.last().unwrap() < 0 {
            0
        }
        else {
            for i in (0..v.len()).step_by(2) {
                v[i] -= v[i+1] - 1
            }
            v.pop();
            1
        }
    }
}

fn f(S: String) -> i64 {
    // "114111" -> [-2, 4, -3]
    let mut v = to_vec(S);
    if v.is_empty() {
        return -1
    }
    
    let s0 = normalize(&mut v);
    if v.len() == 1 {
        return s0 - v[0] - 1
    }
    
    let mut s: i64 = 0;
    for i in (0..v.len()-2).step_by(2).rev() {
        s = (s - v[i+2] + 1) % D;
        v[i] = (v[i] - s * (v[i+1] - 1)) % D
    }
    (s0 + s - v[0] - 1) % D
}


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

fn main() {
    let S = read_input();
    println!("{}", f(S))
}