【Rust】ABC428まとめ（A~C）

AtCoder Beginner Contest 428

unrated参加してABCの3完52分0ペナでした。
どうしても今週時間が取れず、１週間遅れでの更新になってしまいすみません。
今回はA~Cをまとめていきます。

A - Grandma's Footsteps

高橋くんの走る速度は常に$S$で変わらないため、合計何秒走っているかを求め、その秒数に$S$を掛けることで高橋くんの走った距離を求めることができます。

なお、走った合計の秒数$\text{sum}$は、残り秒数$x$という変数を利用して、以下の要領で簡単に求められます。

• $x \ge A+B$のとき：$\text{sum}←\text{sum} + A$および$x←x-A+B$を代入する
• $x<A+B$のとき：$\text{sum} ← \text{sum} + \min{(A, x)}$を代入して処理を終了する

use proconio::input;

fn main() {
    input! {
        s: usize,
        a: usize,
        b: usize,
        x: usize,
    }

    let mut ans = 0;
    let mut x = x;
    while x > a + b {
        ans += a;
        x -= a + b;
    }
    ans += x.min(a);

    println!("{}", ans * s);
}

B - Most Frequent Substrings

文字列長$K$の文字列をキーとする辞書を定義することによって出現回数を管理し、最大の出現回数を記録した文字列を昇順に出力することでこの問題に正解することができます。

RustではBTreeMapcrateが存在し、自動でソート済み辞書を定義することができるため、それを利用することで簡潔に解答することができます。

use itertools::Itertools;
use proconio::input;
use proconio::marker::Chars;
use std::collections::BTreeMap;

fn main() {
    input! {
        n: usize,
        k: usize,
        s: Chars,
    }
    let mut map = BTreeMap::new();
    for i in 0..=n - k {
        *map.entry(s[i..i + k].iter().collect::<String>())
            .or_insert(0) += 1;
    }
    let max = map.values().max().unwrap();

    println!("{}", max);
    println!(
        "{}",
        map.iter()
            .filter(|(_k, v)| *v == max)
            .map(|(k, _v)| k)
            .join(" ")
    );
}

C - Brackets Stack Query

良い括弧列となる必要条件を考えましょう。
まず考えやすいところとして(と)の個数は合っていなければなりません。

次に、今回は「末尾に追加する」「末尾を削除する」のように、末尾への操作しかありません。
このため、(より右に)が来なければならないという一方向性に着目すると、どこかで(よりも)の方が（左から数えて）多くなってしまったタイミングで、その位置を改めて排除しない限り良い括弧列にはならないということがわかります。

▼(よりも)の方が多くなってしまうと、良い括弧列を作ることができない例

したがって、そのような位置を記録する破綻フラグを用意しておくことで、

• 破綻フラグの示す位置が削除されていない場合はNo
• 破綻フラグの示す位置が削除されているが(と)の個数が一致しない場合No
• 破綻フラグの示す位置が削除されており(と)の個数も一致する場合Yes

のような場合分けが成立します。
あくまで一例ですが、ACコードを載せておきます。

use proconio::input;
use itertools::Itertools;

fn main() {
    input! {
        q: usize,
    }

    let mut ans = vec![];
    let mut should_remove = 0;
    let mut height = 0;
    let mut st = vec![];
    for _ in 0..q {
        input! {
            i: usize,
        }
        if i == 1 {
            input! {
                c: char,
            }
            st.push(c);
            if c == '(' {
                height += 1;
            }else {
                height -= 1;
                if should_remove == 0 && height == -1 {
                    should_remove = st.len();
                }
            }
        }else {
            if let Some(x) = st.pop() {
                if x == '(' {
                    height -= 1;
                }else {
                    height += 1;
                }
                if should_remove > st.len() {
                    should_remove = 0;
                }
            }
        }

        if should_remove == 0 && height == 0 {
            ans.push("Yes");
        }else {
            ans.push("No");
        }
    }

    println!("{}", ans.iter().join("\n"));
}

まとめ

今回はBTreeMapやItertoolscrateの色々なメソッドを学ぶことができました。
また、知人からRustの競プロ用ライブラリを共有いただくこともできたので、これらをもっと使い慣れられるよう頑張ります。