🐕

ABC033 C - 数式の書き換え Rust

2021/02/10に公開

Rust

AtCoder

競プロ

tech

問題

1 桁の整数、”＋”(加算)、”＊”(乗算)からなる数式 S が与えられる。乗算を優先して計算する。最小限の数字を 0 に変更することで、この式の値を 0 にせよ。

制約

1 <= |S| <= 100,000

考えたこと

”＋”のあいだに 0 が含まれない区間を数えれば OK。計算量は O(N)。

乗算によって複数の数字は 1 つの数に集約されるので、乗算後に残るのは、”＋”で分けられた数字になります。さらに、”＋”間の区間に 0 があると、乗算後、その区間の数字は 0 になるため、書き換えの必要はありません。

実装の方針としては、各区間に 0 が含まれるかの配列 Vec<Boolean>を用意します。予め数式 S の最初の数字を入れておきます。

その後、S.chars()のイテレータを回して、以下の操作を行います。

文字が”＊”なら、配列の最後の要素と、”＊”の次の数字のどちらかが 0 でないか論理和を取ります。
文字が”＋”なら、”＋”の次の数字が 0 かどうかの判定結果を push します。

最後に、filter 関数で false(0 ではない)要素を数えます。

コード

use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to token")
}

fn main() {
    let s: String = read();
    let mut s = s.chars();
    let is_zero = |c: Option<char>| -> bool {
        c.unwrap() == '0'
    };
    let mut v = vec![is_zero(s.next())];
    while let Some(x) = s.next() {
        if x == '*' {
            let vl = v.len();
            v[vl - 1] |= is_zero(s.next());
        } else if x == '+' {
            v.push(is_zero(s.next()));
        }
    }
    println!("{}", v.iter().filter(|&&x| !x).count());
}

問題

制約

考えたこと

コード

Discussion