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

A問題

解法

問題文のReLU関数をそのまま実装する

注意点

負の値が与えられることに注意

ソースコード

use proconio::{fastout, input};

#[fastout]
fn main() {
    input! { x: isize }

    println!("{}", if x < 0 { 0 } else { x });
}

B問題

解法

ゴールの座標をｘ軸に対称な場所に取り直し、スタートとゴールを結ぶ直線とｘ軸との交点を求めることで答えを求めることができる。 よって答えを求めるための１次関数 $y = ax + b$ の定数 $a, b$ は $$ a = \frac{G_y - S_y}{G_x - S_x} $$ $$ b = S_y - a*S_x $$ ただし、 $G_x$ はマイナスをかけ直した値。

これより、ｙが０のときのｘが答えとるので $$ x = - \frac{b}{a} $$

注意点

• 少数の誤差
• 計算時の符号

ソースコード

use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        sx: f64,
        sy: f64,
        gx: f64,
        gy: f64,
    }

    let gy = -gy;
    let a = (gy - sy) / (gx - sx);
    let b = sy - a * sx;

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

C問題

解法

すべての経路を探索するには順列全探索を使う。 制約が、 $2 \le N \le 8$ なので $O(N \times N!)$ でも間に合う。

ソースコード

use itertools::Itertools;
use proconio::{fastout, input};

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

    println!(
        "{}",
        (1..n)
            .permutations(n - 1)
            .filter(|perm| {
                let mut time = t[0][perm[0]] + t[perm[n - 2]][0];
                for i in 0..(n - 2) {
                    time += t[perm[i]][perm[i + 1]];
                }
                time == k
            })
            .count()
    );
}

D問題

解法

いもす法 を使うことで $O(N + max(T_i))$ で解くことができ、間に合う。 時間は $min(S_i)$ から $max(T_i)$ が扱える配列を用意し記録する。

ソースコード

use proconio::{fastout, input};

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

    let mut water = [0; 200000 + 1];
    for (s, t, p) in stp {
        water[s] += p;
        water[t] -= p;
    }
    let mut using = 0;
    for u in water.iter() {
        using += u;
        if using > w {
            println!("No");
            return;
        }
    }
 
    println!("Yes");
}