【AtCoder Beginners Selection】全10問をRustで解いた。

2022-02-28

はじめに

santaってアプリでTOEICの勉強をはじめました。数分やってワイの何が分かるんだと思いならもAIくんが、君は650点ぐらい取れるよっていうてくれたので嘘でも気分が良かったです。好きになったので毎日数分ずつでも愛でようと思いました。

ワイのTOEIC実スコアは、上司から「お前の入社時のTOEICスコアを見たけど、信じられないぐらい低いな。昇給条件にもなってるから今からでも上げておけよ」と言われたり、海外の製品作ってるエンジニアにここの動きどうなってんの？と問い合わせ打ち合わせが設定されてしまったときに困ったり、英語で説明して貰ったのに大味な回答しか理解できないのに「どうや？」って聞かれて「Thank you for ansewer!I’m cleary」とあってるのか良くわからん回答しか咄嗟にでなくて非常に情けない気持ちになったのがきっかけです。せめて、気の利いた一言を言いたい。せっかく説明してもらったことの８割ぐらいは理解したいというこの２つのモチベーションです。

英会話とTOEICは違うとか言う輩もいますが、まぁ何もやらんより良いやろ理論でいきます。

長々と前置きを書きましたが、TOEIC一切関係ない話題に移ります。今回の記事は前回、前々回と初めた競技プログラミンの話題です。

細々とやっていた、AtCoder Beginners Selectionの全10問をRustで解いたので記事に残しましたという話をします。

AtCoder Beginners Selection

QiitaにAtCoder に登録したら次にやること～これだけ解けば十分闘える！過去問精選 10 問～という記事があるのですが、とりあえずこれだけ解いとけばいいよって10問が紹介されています。解き方は付いてるのですが、勉強目的もあるので見ないようにしておきましょう。

競プロはよくわからないんで、とりあえず言われたとおり、ここから問題を解いていきましょう。 (AtCoder Beginners Selection) https://atcoder.jp/contests/abs/tasks

事前準備編

今回はRustでやると決めたので、標準入力を受け取る方法を考えます。共通的な関数とか用意すれば良いのかと思っていたのですが、どうも標準入力の受け取りを簡易に済ませるクレートがあるようです。使っていきましょう。

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つのテキストデータを受け取り、出力すれば完了。 Hello Worldみたいもんですわ。

ABC086A Product

受け取った入力の積が偶数か、奇数かを求める問題です。 if文がでてきましたね。まだ悩むことも無いぐらいの話かと思います。

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

プログラムを勉強始めたての人が取り組むのにちょうど良さそうなコンテンツだなと思っていた時期です。

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 OR 1010b OR 1110b = 1110b

が得られるためこの値に対して右シフトを繰り返していきます。下一桁に1が来なければ偶数と判断できますので、奇数が来るまでの回数をカウントしました。

ABC085B - Kagami Mochi

直径Ncmの円形の餅が複数入力に入ってきます。下の段から大きい順に積み上げたとき、何段になりますか？というのを求める問題です。制約として上に積み上げることのできる餅は、下の段の餅よりも小さいこと。同じ大きさのものは積めません。

それを求めるため、私の書いたコードはこちら。

入力された値を大きいものから順番に並べて、取り出した値を比較します。小さい場合は、＋１するように書きました。

use proconio::input;

fn main() {
    input! {
        n: usize,
        mut a: [i32; n]
    }
    a.sort();
    a.reverse();

    let mut x = 1;
    let mut now = 0;
    for v in a {
        x += if now > v { 1 } else { 0 };
        now = v;
    }
    println! {"{}",x}
}

通ったのは通ったのですが、もっといい方法があるんじゃないかと思い、他の人のコードを見てました。 https://atcoder.jp/contests/abs/submissions/29420210

cargo add proconio itertools

でまとめてクレートを追加します。

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

fn main() {
    input! {n:i32, d: [i32; n]}
    println!("{:?}", d.into_iter().unique().collect_vec().len());
}

勉強のため何をしているのか見てみてみます。 into_iterを使うと、所有権を持つイテレータが作成し、操作できるイテレータを作成しています。その後、unique()関数で重複した値を消去して、collect_vec()を使いイテレータをベクタ型に戻し、長さを取得すれば求めていた値が出るわけですね。

なるほどなぁ。

ABC087B - Coins

指定された枚数の中で、指定された額に到達する組み合わせが何パターンあるかを数える問題です。 500円、100円、50円の組み合わせのパターンを数え上げようと思います。

use proconio::input;

fn main() {
    input! {
        a: u32,
        b: u32,
        c: u32,
        d: u32,
    }
    let mut ans = 0;
    let mut sum = 0;

    for i in 0..a + 1 {
        //50円ループ
        for j in 0..b + 1 {
            //100円ループ
            for k in 0..c + 1 {
                //500円ループ
                sum = (i * 500) + (j * 100) + (k * 50);
                if sum == d {
                    ans += 1;
                }
            }
        }
    }

    println! {"{}",ans}
}

入力の制約が各枚数50が上限だったので、組み合わせ的にはそこまでべらぼうな数にもならんだろうとこの解法を試しました。通ったので良しとしましょう。

ABC083B - Some Sums

1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を求めてください。

各桁の値を取り出して足し算した値を求め、指定されたA～Bに収まっているものの合計を求めます。

桁の取り出しを丁寧？にやろうとしたのがこちら。

#![feature(int_log)]
use proconio::input;

fn main() {
    input! {
        n: usize,
        a: usize,
        b: usize,
    }
    let mut ans = 0;
    let base = 10 as i32;
    for i in 1..n + 1 {
        let dig = i;
        let mut sum = 0;

        let k = i.log10() + 1;

        for j in 0..k {
            let pow = base.pow(j) as usize;
            sum += (dig / pow) % 10;
        }

        // A 以上 B 以下
        if a <= sum && sum <= b {
            ans += i;
        }
    }
    println! {"{}",ans}
}

↑log10で桁数を求めて、丁寧に求めてたんですがそもそも各桁の値が欲しいだけなら下のやり方で良いなと思い書き直しました。最終的に出したのがこのコード。

use proconio::input;

fn main() {
    input! {
        n: usize,
        a: usize,
        b: usize,
    }
    let mut ans = 0;
    for i in 1..=n {
        let mut dig = i;
        let mut sum = 0;

        while dig > 0 {
            sum += dig % 10;
            dig /= 10;
            if dig == 0 {
                break;
            }
        }
        if a <= sum && sum <= b {
            ans += i;
        }
    }
    println! {"{:?}",ans}
}

ABC088B Card Game for Two

問題文
N 枚のカードがあります. i 枚目のカードには, a
i

  という数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

解き方の方針を考えます。標準入力の一覧をソートして、Stackに詰め込んでいき交互にpopして合計の差を求めたらどうかと思います。やってみましょう。

use proconio::input;

fn main() {
input! {
    n: usize,
    a: [i32; n]
}
let mut vec = a;
vec.sort();

let r = vec.len()-1 as usize;

let mut alice = 0;
let mut bob = 0;
let mut cnt = 0;
for i in 0..=r {
    if cnt %2 == 0{
        alice += vec[r-i];
    }else{
        bob += vec[r-i];
    }
    cnt += 1
}
println!{"{}",alice-bob}
}

標準入力をVectorに詰め込んで、Sortする。数値の大きい方から順繰りに取り出して、aliceとBobに交互に詰め込んで回答としました。

まだ冗長だったので、もう少し考えてみます。調べてみると、VecでSortしたあと逆順にすることもできそうだったので試しました。 pythonみたいなiterやenumerateもあるかなと探したらあったのでこれも使います。

AliceとBobそれぞれで値を求めてから最後、引き算してましたが、最終的に求めたいものが、差なので集計するときに、Bobの方だけ -1 をかけて負の値で足し算すればいいですね。

use proconio::input;

fn main() {
    input! {
        n: usize,
        mut a: [i32; n]
    }
    a.sort();
    a.reverse();

    let mut sum = 0;
    for (i, val) in a.iter().enumerate() {
        sum += if i % 2 == 0 { val * 1 } else { val * -1 };
    }
    println!{"{}",sum}
}

だいぶスッキリしたんじゃないでしょうか。実行時間も 7ms -> 4msに短縮されました。

ABC085C - Otoshidama

青橋君がお年玉をもらったらしいのですが、お札はN枚あって、合計いくらだった　と話していたそうです。問題の主は、「お前ホンマにそんなもらったんか？おぉん？？」となったようでして、N枚の札と合計金額がY円となる組み合わせがあるかを判定するプログラムを書くようです。

信用無いなぁ青橋君。

何も考えずに3重for文で書いてみた。

use proconio::input;

fn main() {
    input! {
        n: usize,
        y: usize,
    }

    for i in 0..=n {
        for j in 0..=n {
            for k in 0..=n {
                if ((10000 * i) + (5000 * j) + (1000 * k)) == y {
                    println!("{},{},{}", i, j, k);
                    return;
                }
            }
        }
    }
    println!("{},{},{}", -1, -1, -1);
}

これだとTimeoutしてしまうので削減していきます。

use proconio::input;

fn main() {
    input! {
        n: u64,
        y: u64,
    }

    for i in 0..=n {
        for j in 0..=n-i {
            if 10000 * i + 5000 * j + 1000 * (n - i - j) == y {
                println!("{} {} {}", i, j, n - i - j);
                return;
            }
        }
    }
    println!("{} {} {}", -1, -1, -1);
}

二重目のループは、最初にi枚使ったとしてその分減らす。 3重目のループはなくして、iとj値から求めることができるので削除。

これでまずは通るようになったのでOKとしましょう。

そういえば、計算量が多くてWAになるのはこの問題からですかね。計算量を意識する必要がでてきました。

ABC049C - 白昼夢

いわゆるC問題ってやつらしいです。 C問題からは、計算量を気にしないと解けない問題に入ってくるようです。全探索すると解けないとかそう話に入ってきます。

与えられた入力に対して、dream,dreamer,erase,eraserという単語をN個並べたときにできる文字列と一致するかという問題です。いくつか解き方があるのですが、思いついたのは指定された単語の数も少ないので正規表現で削除指定しまう方法です。最後、何も文字列が残らなかれば一致したと判定するようにしてみました。

fn main() {
    input! {
        s: String,
    }
    let mut res = s;
    for t in &["eraser", "erase", "dreamer", "dream"] {
        let re = Regex::new(t).unwrap();
        res = re.replace_all(&res, "").to_string();
    }
    if res.is_empty() {
        println!("YES")
    } else {
        println!("NO")
    }
}

正規表現を使わずとも文字列操作で消せるんではないかと思わなくは無いですが、まぁいいでしょう。

ABC086C - Traveling

旅行プランを建てる問題です。グリッド上のマス目を移動する鹿が時刻tのときに指定したポイントに移動することができるかを調べる方法です。実際にマス目を移動して、シミュレーションする方法も考えられましたがそれだと時間超過するんだろうなと考えました。

方針を考えた結果

現在のtと次tとの差を求め移動できる数と、移動する必要のあるマスを求めてたどり着けるかを求める
移動できる数と移動に必要なマスがそれぞれ偶数、奇数かと求め比較します。

1で明らかに足りていない子達を弾いて、2で移動数的には足りてるんだけどちょうどたどり着けない子達を弾きます。移動できる数と、移動に必要なマス同じ偶数か奇数の場合、マス往復して時間調整してゴールにたどり着くことができます。

ここまで思いついたのであとは書くだけです。

use proconio::input;
fn main() {
    input! {n:usize, v: [[i32; 3];n]}

    let mut bt = 0;
    let mut bx = 0;
    let mut by = 0;
    let mut b = false;
    for p in 0..n {
        let t = v[p][0];
        let x = v[p][1];
        let y = v[p][2];

        let mp = t - bt;
        let cp = (x - bx).abs() + (y - by).abs();
        if mp < cp {
            b = true;
            break;
        }
        if mp % 2 != cp % 2 {
            b = true;
            break;
        }
        bt = t;
        bx = x;
        by = y;
    }
    if b != true {
        println!("Yes")
    } else {
        println!("No")
    }
}

もっと短くすることもできそうな気はしますが、まずはこれで動かして通しました。

全10問解いた

途中TOEIC受けたりと、思いの外時間がかかってしまいましたがビギナー向け10問をRustで書きました。過去の記事の内容も含めて、この記事に10問全て集約しました。競プロ界隈の人たちからするとこんなことでｗｗｗみたいな感じなのかもしれませんがなんか達成感ありますね。ゲームを全クリしてエンディング見るような感じ。ゼノサーガ１をクリアしたときこんな感じでしたね。次は、２やろっとみたいな感じでした。

まとめ

AtCoderは他の人のコード見れるのでいいですね。自分が書いたコードよりも早くて短いコードや、別のやり方で解いているやり方を見ることができるのが良いですね。ゲーム感覚で結構楽しかったのでまた面白そうなのがあれば解いていこうと思います。今のところ転職する気は無いのですが、TOEICと競プロのレベルを上げるとおちん○んの高い職が見つかったり、副業で高単価の仕事が舞い込んで来たりするようなので、気長に上げていきたいなと思います。