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