AtCoder Beginner Contest 418 D

https://atcoder.jp/contests/abc418/tasks/abc418_d

00なら1に10なら0になどとなるので、1の個数の偶奇が文字列の長さが1短くなるごとに変わります。すなわち、文字列の長さが偶数なら1の数が偶数なら美しい数、奇数ならそうでない、などとなります。

ここが右端となる部分文字列の美しい文字列とそうでない文字列の数をDPで求められます。

// XNOR Operation
#![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()
}


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

type DP = (usize, usize);

fn initialize_dp(cs: &Vec<char>) -> Vec<DP> {
    let N = cs.len();
    let mut dp: Vec<(usize, usize)> = vec![(0, 0); N];
    if cs[0] == '0' {
        dp[0] = (0, 1)
    }
    else {
        dp[0] = (1, 0)
    }
    dp
}

fn update_dp(c: char, prev_dp: DP) -> DP {
    let (a, b) = prev_dp;
    if c == '0' {
        (b, a + 1)
    }
    else {
        (a + 1, b)
    }
}

fn F(S: String) -> usize {
    let cs: Vec<char> = S.chars().collect();
    let N = cs.len();
    let mut dp = initialize_dp(&cs);
    for i in 1..N {
        dp[i] = update_dp(cs[i], dp[i-1])
    }
    dp.iter().map(|&(a, _)| a).sum::<usize>()
}

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