Rustの基礎文法大体覚えたので競プロで理解を確かめていこう(中盤)

2022-02-22

はじめに

2日目です。育児と残業厳しい中ポチポチ進めています。実装方針を立てるまではいいのですが、Rustを書くのに結構引っかかってますね。今日中には全部とき終えたかったのですが、タイムアップです。

あと発見というほどでもないですが・・・競プロだと普段あまり気にもかけない実行時間（計算量）を意識するようになりますね。

これ、私生活や仕事で何か求めるときに書き捨てるコードだと意識することがないなと思ってます。ちゃんと考えろよハゲ。なめてんのか。とか言われる気もしますが……。

言い訳としては、繰り返し使うようなものでもなく、書き捨てるだけのコードなら結果を得られるまでに数秒ぐらいの差は誤差として、短くしたり計算量減らすために思案するのに時間をかけず、コード書く時間を短縮する方がいいんじゃないかと思ったりもします。（時間かけてもそんなスマートなやつ書けないですけどね……）

AtCoder Beginners Selection

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

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

事前準備編

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

cargo add proconio

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に短縮されました。