【AtCoder】Rustを勉強するため、AtCoder Beginners Selectionを解いていく(前半戦)

2022-02-21

はじめに

業務とか趣味でソフトを書くことが多々あるのですが、 愚直に処理を書いており、遅いウンコードを沢山生成してきたことを悔いています。

規模の小さいソフトとか、使い捨てコードであれば十分ですが、 凝ったことをやろうとしたり、可読性の良いコードを書くために使える手札があまりにも少ないことに危機感を覚えてました。

それとは別に、少し前からRustを触り始めたのですが文法を眺めて試していくのも飽きてきたところです。

そういえば、友人や先生が競プロを始めてたのをふと思い出しました。 どのぐらいできるのかと力試しで、Paizaのランク上げに2日間ほど勤しんでおり、Bランクまで上げることはできました。(各ランクの問題を1問解いたら昇格なので難易度は低い?)

これは余裕っすわ!とAランク問題を2問ほど解いていたのですが、 恥ずかしながらテストケースを満たすコードは書けても実行時間で弾かれましてね・・・。

計算量を考えないクソコードでは通らないってことですよ。

こうなってくると、せめてAランクぐらいは行きたいなという思いと、 Rustの勉強兼ねて競プロを始めよういう気持ちになっております。

とりあえず競プロやろうにも、何から手を付けらたいいのかよくわからなかったんで、 AtCoder Beginners Selectionを解いて見ることにします。

これが無事終わったら競プロ典型90問に手を出していきます。 90問が終わる頃には随分と逞しく育っていることを期待しています。

気長にやっていきましょう。

AtCoder Beginners Selection

QiitaにAtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~ という記事があるのですが、とりあえずこれだけ解いとけばいいよって10問が紹介されています。

競プロはよくわからないんで、とりあえず言われたとおりやっていこうと思います。 (AtCoder Beginners Selection) https://atcoder.jp/contests/abs/tasks

事前準備編

標準入力の受け取りを簡易に済ませるために、こちらのクレートを使用します。

cargo add proconio

PracticeA - Welcome to AtCoder

標準入力を受け取って、出力するコードを書く問題です。

use proconio::input;

fn main() {
    input! {
        a: i32,
        b: i32,
        c: i32,
        s: String,
    }
    println!("{} {}", a + b + c, s);
}

3つの数字と1つのテキストデータを受け取り、出力すれば完了です。

ABC086A Product

受け取った入力の積が偶数か、奇数かを求める問題です。 とりあえずこんな風に書きました。

fn main() {
    input! {
        a: i32,
        b: i32,
    }
    let c = a * b;
    if c % 2 == 0 {
        println!("{} ", "Even");
    } else {
        println!("{} ", "Odd");
    }
}

if文の使い方を覚えるのにちょうど良い塩梅です。

ABC081A Placing Marbles

数字の1と0を使って、該当するマスにビー玉が置かれているか、置かれていないかを表現してる問題です。 例えば、101と書かれたら 1マス目と3マス目にビー玉が入っています。

問題は、与えられた入力に対して何個ビー玉が置かれているかを求める問題です。

こんな風に書きました。

use proconio::input;

fn main() {
    input! {
        a: String,
    }
    let mut c = 0;
    for i in a.as_str().chars() {
        if i == '1' {
            c += 1;
        }
    }
    println!("{}", c);
}

文字列として受け取り、1文字ずつ見て、1なら個数を加算して結果を出してます。 数値として扱う方法もありそうですがこの方法が楽そうだったので採用しました。

ABC081B Shift only

与えられた数値をひたすら2で割り奇数がでるまでの回数を求める問題です。 タイトルの通りシフト演算を使うことが求められているのでそのやり方でやってみます。

use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [usize; n]
    }
    let mut b = 0;
    let mut ans = 0;

    for i in 0..n {
        b = a[i] | b;
    }

    while (b & 1) == 0 {
        b = b >> 1;
        ans += 1;
    }
    println! {"{}",ans}
}

1つ目のforループですべての数字のORを求めています。 与えられた数字のORを取るとこのような感じになります。 1000b 1010b 1110b


1110b が得られます。

下一桁に1が来なければ偶数である。 while文の中で、下一桁に1が来るまで右シフト(2での割り算)を繰り返し、その回数をカウントしています。

それぞれの実行結果も載せておきます。

2022-02-22 00:09:27 ABC081B - Shift only kenpos Rust (1.42.0) 200 296 Byte 5 ms 2132 KB 詳細 2022-02-21 03:52:13 ABC081A - Placing Marbles kenpos Rust (1.42.0) 100 225 Byte 7 ms 2148 KB 詳細 2022-02-21 03:19:42 ABC086A - Product kenpos Rust (1.42.0) 100 224 Byte 6 ms 2084 KB 詳細 2022-02-21 03:07:53 PracticeA - Welcome to AtCoder kenpos Rust (1.42.0) 100 170 Byte 6 ms 2160 KB 詳細

残り6問も引き続き解いていこうと思います。全部解けたらまとめた記事にします。

まとめ

またなんか新しいこと始めよったぞ。 お見守りください。