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

rustでA~Cまで

A問題

解法

１日毎に色が変わるため、２で割ったあまりを使えば良い。

注意点

偶数が白、奇数が黒

ソースコード

use proconio::{input, fastout};

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

    println!("{}",
        if n % 2 == 0 {
            "White"
        } else {
            "Black"
        }
    );
}

B問題

解法

$i$ 回目の操作で書き出される整数の合計が、 $[A_i,B_i]$ の和なので、１から任意の数までの和を求める公式を使って、 $$ \frac{1}{2} (B_i+1)\times B_i - \frac{1}{2} (A_i-1)\times A_i $$ とすることで求まる。これをすべての入力に対して行うことで答えが求まる。

注意点

A以上B以下でどちらの数も含むことに注意する。

ソースコード

use proconio::{input, fastout};

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

    println!("{}",
        ab.iter()
            .map(|&(a, b)|{
                b*(b+1)/2 - a*(a-1)/2
            })
            .sum::<usize>()
    );
}

C問題

解法

成約が $3 < N < 10^{2}$ と小さいので、 $O(N^{3})$ の全探索で間に合う。

与えられたケースから、３点が一直線上に並んでいることを判定するのは難しいので、1点が原点になるように平行移動することで計算しやすくなる。 他の2点は1点が原点にあるので、原点からの向きが等しいか逆ベクトルであれば一直線上に3点が並んでいると言える。

また、ベクトルの向きは2点を $(x_1, y_1), (x_2, y_2)$ とすると、 $$ \vec{p_1} = y_1 / x_1, \vec{p_2} = y_2 / x_2 $$ で表せ、これが等しいとき一直線上にある。

注意点

割り算を使うと計算誤差が出てしまう可能性があるため、 $\vec{p_1} = \vec{p_2}$ を計算し、 $$ y_1 \times x_2 = y_2 \times x_1 $$ で判定する。

ソースコード

use proconio::{input, fastout};

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

    for i in 0..n {
        for j in (i+1)..n {
            for k in (j+1)..n {
                let x1 = xy[j].0 - xy[i].0;
                let y1 = xy[j].1 - xy[i].1;
                let x2 = xy[k].0 - xy[i].0;
                let y2 = xy[k].1 - xy[i].1;
                if x1*y2 == x2*y1 {
                    println!("Yes");
                    return;
                }
            }
        }
    }
    println!("No");
}

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

緑になりたい茶コーダーの精進記録です。 B問題までで、Rustでの回答です。

A問題

解法

AとBを順番に見ていき、全探索をする。

成約が、$N \leq 10^{18}$なので、 $$ A \leq log_3 {10^{18}} \fallingdotseq 37 $$ $$ B \leq log_5 {10^{18}} \fallingdotseq 25 $$ となり、計算量は$O(AB)$で間に合う。

注意点

問題ではA,Bが、条件を満たす正の整数の組なので、０は含まない。

$1 \leq N \leq 10^{18}$なので、オーバーフローしない型(64bit整数型以上)を使って計算する。

ソースコード

use proconio::{input, fastout};

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

    let mut three = 3u64;
    for i in 1..=37 {
        let mut five = 5u64;
        for j in 1..=25 {
            if three + five == n {
                println!("{} {}", i, j);
                return;
            }
            five *= 5;
        }
        three *= 3;
    }
    println!("-1");
}

B問題

解法

ポイントは、

• 問題文より、$a_x$と$a_y$は、片方を+1するともう片方を-1するので、２つの和は変わらない。
• 複数の頂点がつながっていた場合も上が成り立つので同じグループの和は常に変わらない。
• bの場合も同じことが言える。

よって、union findデータ構造を用いることで集合を管理し、親が同じもの同士では和が変わらないことを利用し、その集合のaを順に足していきbを順に引いていくことでその集合の値が0になれば目的を達成することができると言える。

注意点

与えられるc,dが1-besed-indexで、a,bは0-besed-indexなのでインデックスを合わせるためにマージするときにc,dから1引く。

a,bはマイナスもあるので、unsignedの型は使わない

テストケースによっては、 $$ -10^{9} \leq a,b \leq 10^{9} $$ $$ 1 \leq N \leq 2 \times 10^{5} $$ なので、 $10^{9} \times 10^{5} = 10^{14}$となるため、オーバーフローに気をつける。

ソースコード

union find(Dsu)のライブラリはここからお借りした。 また、長くなるためDsuの部分のコードは省略する。

use proconio::{input, fastout};

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

    let mut uf = Dsu::new(n);
    for (c, d) in cd { uf.merge(c-1, d-1); }
    let mut ans = vec![0isize; n];
    for (i, (&a, &b)) in a.iter().zip(b.iter()).enumerate() {
        ans[uf.leader(i)] += a - b;
    }

    println!("{}",
        if ans.iter().all(|&x|{ x==0 }) {
            "Yes"
        } else {
            "No"
        }
    );
}

ABC180復習＆解説[Rust]

早く緑になりたい茶コーダーの記録です。

D問題までで、Rustでの回答です。

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);
}