【AtCoder】ABC182復習＆解説【Rust】

rustでA~C

A問題

解法

現在の数 $B$ にいくつ数を足せば $2A + 100$ になるか、と読むことができる。

よって、 $$ 2A + 100 - B $$ を計算することで求まる。

ソースコード

use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        a: isize,
        b: isize,
    }

    println!("{}", 2 * a + 100 - b);
}

B問題

解法

$N, A$ が十分小さいため、全探索をし最も割り切れる $A$ が多い数を調べる。

ソースコード

use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }

    println!(
        "{}",
        (2..=1000)
            .max_by_key(|&x| { a.iter().filter(|&y| { y % x == 0 }).count() })
            .unwrap()
    );
}

C問題

解法

bit全探索を行い、3の倍数ができる集合のうち最も要素数の多いものを探す。 制約が $1 \le N \lt 10^{18}$ だが、桁で考えるため18までを考えればよく、 $O(2^{N})$ のビット全探索でも間に合う。

注意点

• 使う桁数ではなく、消す桁数を求める。
• 作ることができない（消す桁数と入力の桁数が等しい、使う桁数が０）なら、-1を出力。

ソースコード

use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        mut n: usize,
    };

    let mut dig = Vec::<usize>::new();
    while n != 0 {
        dig.push(n % 10);
        n /= 10;
    }
    let ans = (0usize..1 << dig.len())
        .map(|bit| {
            let mut digsum = 0;
            for i in 0..dig.len() {
                if (1 << i) & bit != 0 {
                    digsum += dig[i];
                }
            }
            if digsum % 3 != 0 {　return 0;　}
            bit.count_ones() as usize
        })
        .max()
        .unwrap();

    println!(
        "{}",
        if ans == 0 {
            -1
        } else {
            (dig.len() - ans) as isize
        }
    );
}