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

AtCoder Beginner Contest 415

お疲れ様です。
一年ほどJavaScriptで競技プログラミングを行ってきましたが、これからはRustを書くことにしました。
理由としては次の五つです。

• JavaScriptというプログラミング言語の知見がある程度得られたため
• クライアントサイドではなく、サーバサイドの言語を学びたいと思ったため
• インタプリタ言語ではなく、コンパイラ言語を学びたいと思ったため
• 競技プログラミング的にそもそもJavaScriptは不利なため
• JavaScript専用のonline-judge-toolsが利用できなくなってしまったため

しばらく慣れるまではRated参加することはないと思いますが、その間は簡単な感想記事を上げることにしました。
新米Rustaceanですが、どうぞよろしくお願いいたします。

今回はRustでバーチャル参加しました。
文法を調べつつやりABCの三完でした。
A~Cまでまとめます。

A - Unsupported Type

$A$の中に$X$があるかどうかを調べます。
JavaScriptではincludes()メソッドですが、Rustではcontains()メソッドで簡単に判定できるようです。

use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [i32; n],
        x: i32,
    }
    
    println!("{}", if a.contains(&x) { "Yes" } else { "No" });
}

B - Pick Two

区画の左から順番に荷物を二個ずつ選べば良いということで、いろいろな解法があると思いますが、あらかじめ配列$\text{arr}$に荷物のあった区画の情報を入れておいて、二個ずつ取り出していけば良さそうです。

..###..#.##
arr = [3,4,5,8,10,11]
ans = ["3,4", "5,8", "10,11"]

use proconio::input;

fn main() {
    input! {
        s: String,
    }

    let mut arr = vec![];
    for (i, c) in s.chars().enumerate() {
        if c == '#' {arr.push(i + 1);}
    }

    let mut ans = vec![];
    for i in (0..arr.len() - 1).step_by(2) {
        ans.push(format!("{},{}", arr[i], arr[i + 1]));
    }

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

}

C - Mixture

薬品を一つずつ取り除いていって、危険な状態に遷移せず何もない状態になることができるかどうかを考えました。
例えば$N=3,S=$0010000のとき、薬品iが混ざっているかどうかを$3$桁のbit文字列で表すことにする（1のとき薬品が混ざっている）と、111→101→001→000のように薬品を取り除くことで危険な状態に遷移せず何もない状態にすることができます。
（物理的には薬品を取り除くのは難しいため、薬品を追加していけるかどうかを見るのが自然なのですが、どちらでも解くことができます）

dfsをイメージして解きましたが、実質bitDPですね。

use proconio::input;
use proconio::marker::Chars;

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

    fn dfs(s: &[char], reachable: &mut Vec<bool>, cur: usize) {
        if cur == 0 {
            return;
        }

        if s[cur - 1] == '1' {
            return;
        }

        for i in 0..32 {
            if (cur & (1 << i)) != 0 {
                let nex = (cur ^ (1 << i));
                if nex == 0 {
                    reachable[0] = true;
                }else if s[nex - 1] == '0' && !reachable[nex] {
                    reachable[nex] = true;
                    dfs(s, reachable, nex);
                }
            }
        }
    }

    let mut ans = vec![];
    for _ in 0..t {
        input! {
            n: usize,
            s: Chars,
        }

        let mut reachable = vec![false; (1 << n)];
        reachable[(1 << n) - 1] = true;
        dfs(&s, &mut reachable, (1 << n) - 1);
        if reachable[0] {ans.push("Yes")} else {ans.push("No")};
    }
    println!("{}", ans.join("\n"));
    
}

まとめ

Rustを初めて書いてみた感想としては、マクロや所有権などRust独特の機能が多く、慣れるのが大変そうな印象です。
本記事で挙げたコードはRustらしくないところが多々あると思います。
競技プログラミングをRustでやっている有名人は結構多い気がするので、いろんな方の書きっぷりから学んでみようと思います。