〈Rust入門〉ABC 105の問題をRustで解いてみる

昨日のABC 105の問題（A〜D）をRustで解いてみた。

以下、read(), read_vec() は

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

(→see Rust入門記（チュートリアルからABSまで） - naoya_t@hatenablog)

A - AtCoder Crackers (100)

fn solve(n:i32, k:i32) -> i32 {
    !!(n % k)
}
fn main() {
    let nk = read_vec::<i32>();
    println!("{}", solve(nk[0], nk[1]));
}

→WA
https://beta.atcoder.jp/contests/abc105/submissions/2996062
!!(n % k) だと駄目だった（元の値に戻ってしまうようだ）のでif文に書き換えた。
Rustのif文は式なので三項演算子的に使える。（※三項演算子そのものはRustには存在しない）

fn solve(n:i32, k:i32) -> i32 {
    // !!(n % k)
    if n % k == 0 { 0 } else { 1 }
}
fn main() {
    let nk = read_vec::<i32>();
    println!("{}", solve(nk[0], nk[1]));
}

→AC
https://beta.atcoder.jp/contests/abc105/submissions/2996098

B - Cakes and Donuts (200)

昨日の解説放送*1の解法で。総当たり。

fn solve(n:i32) -> bool {
    for i in 0..26 {
        for j in 0..15 {
            if i*4 + j*7 == n {
                return true
            }
        }
    }
    false
}
fn main() {
    let n = read::<i32>();
    println!("{}", if solve(n) { "Yes" } else { "No" });
}

→AC
https://beta.atcoder.jp/contests/abc105/submissions/2996107

C - Base -2 Number (300)

Vecはstackとして使える。
is_empty()で先頭要素の有無を調べながらやる方式もできなくはないが let Some(top) = st.pop() というイディオムを使うのが良さそう。

fn solve(mut n:i32) {
    if n == 0 {
        println!("0");
        return;
    }
    let mut st = Vec::<i32>::new(); // ここは何ならi8でもOK
    let mut bit = 1;
    while n != 0 {
        if n % (bit * 2) != 0 {
            st.push(1);
            n -= bit;
        } else {
            st.push(0);
        }
        bit *= -2;
    }
    while let Some(top) = st.pop() {
        print!("{}", top);
    }
    println!("");
}
fn main() {
    let n = read::<i32>();
    solve(n);
}

→RE
https://beta.atcoder.jp/contests/abc105/submissions/2996026
1e9までだし、2^29-1 (=0b11111111111111111111111111111) だとi32ではキャリーがオーバーフローするのでは
nをi64に直して再提出
→AC
https://beta.atcoder.jp/contests/abc105/submissions/2996445

ていうか -2 で割りながら行けばi32のままでいいじゃん

fn solve(mut n:i32) {
    if n == 0 {
        println!("0");
        return;
    }
    let mut st = Vec::<i8>::new();
    while n != 0 {
        if n % 2 != 0 {
            st.push(1);
            n -= 1;
        } else {
            st.push(0);
        }
        n /= -2;
    }
    while let Some(top) = st.pop() {
        print!("{}", top);
    }
    println!("");
}
fn main() {
    let n = read::<i32>();
    solve(n);
}

→AC
https://beta.atcoder.jp/contests/abc105/submissions/2996518

D - Candy Distribution (400)

Hashmapの扱いが難しい…
C++だと未登録のキーに対しデフォルト値(0)を出してくれるので何も考えずに map[key]++ みたいなことが出来るのだけれど。
昨日はすべて登録してからmapをイテレートしてnC2を求めていく方式で書いたけど、今日は左に同じ組のがいくつあるか見ながらインクリメントしていく方式（昨日の解説放送方式）で書いてみた。

use std::collections::HashMap;

fn solve(n:i32, m:i32, a:Vec<i32>) -> i64 {
    let mut map = HashMap::<i32,i32>::new();
    map.reserve((n+1) as usize);

    let mut ans:i64 = 0;

    let mut acc:i32 = 0;
    map.insert(acc, 1);
    for i in 0..n {
        acc = (acc + a[i as usize]) % m;

        let count = map.entry(acc).or_insert(0);
        ans += *count as i64;
        *count += 1;
    }

    ans
}

fn main() {
    let nm = read_vec::<i32>();
    let a = read_vec::<i32>();
    println!("{}", solve(nm[0], nm[1], a));
}

→AC
https://beta.atcoder.jp/contests/abc105/submissions/2996300

Rustで全完できた〜！

*1:りんごさんが渡米中のためみょんみょん＋彼女さんによる放送だった。