A問題

問題分をそのまま実装すれば良い。 N個のボールがあり、A個のボールを取り出すため、箱の中のボールは $N - A$ 個になり、新たにB個のボールを入れるため $N - A + B$ 個になり、これが答えとなる。

use proconio::{input, fastout};

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

    println!("{}", n-a+b);
}

B問題

これも問題分をそのまま実装すれば良い。ただし、注意すべき点があり、

成約が $1\leq N\leq 10^{5}$ , $-10^{5} \leq x_i \leq 10^{5}$ なので、ユークリッド距離を求めるとき最悪の場合 $(10^{5})^{2} * 10^{5} = 10^{15}$ となってしまうためオーバーフローに注意しなければならない。
誤差が $10^{-9}$ 以下であれば正解なのでそれ以上の精度が出るようにで計算しなければならない。

use proconio::{input, fastout};

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

    println!("{}",
        x.iter()
            .map(|a|{
                a.abs()
            })
            .sum::<isize>()
    );

    println!("{}",
        (
            x.iter()
                .map(|a|{
                    a*a
                })
                .sum::<isize>() as f64
        ).sqrt()
    );

    println!("{}",
        x.iter()
            .map(|a|{
                a.abs()
            })
            .max()
            .unwrap()
    );
}

C問題

これは約数を全列挙する問題だと読み替えることができる。高速に約数を求める方法として、 $O(\sqrt{N})$ で求める方法がある。

例えば、12の約数は

1, 2, 3, 4, 6, 12

であり、３と４の間を中心として反対側の数とかけると１２になることがわかる。この中心は $\sqrt{12}$ であり、ここまでを見れば反対の約数もわかる（12の場合、3がわかれば $12 \div 3 = 4$ で4もわかる）ためそれ以降見なくて良くなる。よって、１から順番に見ていき、 $x*x \leq n$ の条件を満たさなくなるところで計算を終わる。

注意すべき点として、約数かどうか調べる数を $i$ とすると、 $i^{2} = n$ になってしまった場合、反対側も計算してしまい同じ数が２つになってしまう（例として９の場合、 $i = 3$ だと3が答えとしてふたつ出来てしまう）ため、省く必要がある。

use proconio::{input, fastout};

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

    let mut ans = Vec::new();
    for i in (1..).take_while(|x| x*x <= n) {
        if n % i == 0 {
            ans.push(i);
            if i*i != n { ans.push(n/i); }
        }
    }
    ans.sort();

    for t in ans {
        println!("{}", t);
    }
}

D問題

この問題は、掛け算はシミュレーションし、足し算は計算する。

掛け算の時を考えると成約は、 $2 \leq A \leq 10^{9},1 \leq N \leq 10^{18}$ なので、Aが最小の２のとき(一番計算することになるとき)でも $\log_2{10^{18}} \fallingdotseq 59$ 回の計算で済む。

また、足し算のときは $1 \leq B \leq 10^{9}$ なので最悪の場合 $10^{9}$ 回計算することになり間に合わないため、 $(y - x) \div b$ で求める。

掛け算と足し算の使い分け方だが、足し算は一定ずつ経験値が増えていくが、掛け算は現在の経験値が少ないうちは少量しか増えず逆に経験値が多いときは大量に増える。このことを利用して、掛け算を行ったときの増加量が足し算を行ったときの増加量を超えるまで掛け算を行い、それ以降は足し算を行えば良い。

経験値が$y$になると進化してしまうことに注意する。 y-1までは進化しないので、掛け算パートでは $a*x \geq y$ でbreakし、足し算パートでは、$(y-1-x)/b$にし、進化させないようにする。

オーバーフローに注意し、64ビットで演算する。 $a*x \gt y \fallingdotseq 10^{18}$ を超えるとオーバーフローするので、オーバーフローが起こる前に、両辺を$a$で割り、 $x \gt y / a$ を計算してあらかじめ確認しておく。

なお、pythonで提出するときにはオーバーフローを気にしなくて良いため、少し実装が楽になり気にかけることも減る。

use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        mut x: u64,
        y: u64,
        a: u64,
        b: u64,
    }

    let mut ans = 0;
    loop {
        if x > y/a { break; }
        if a*x >= y { break; }
        if a*x > x+b { break; }
        x *= a;
        ans += 1;
    }
    ans += (y - 1 - x) / b;

    println!("{}", ans);
}

プログラミングとか色々

プログラミングとかについて色々

ABC180復習＆解説[Rust]

A問題

B問題

C問題

D問題