ABC205 write up

ABC205に参加したのでwrite upを書きます．
めっちゃ久しぶりに参加したのに割とうまく行ったので良かったです

A - kcal

$A$を$1ml$辺りのカロリーに直してあげて$B$と掛けます．小数に注意

a.rs

#![allow(unused_imports)]
#![allow(non_snake_case)]
use cmp::{max, min, Reverse};
use proconio::{fastout, input, marker::*};
use std::collections::*;
use std::*;

fn main() {
	input! {
    a:f64,
    b:f64
	}
  let c:f64 = a/100.0;
  println!("{}",c*b);
}

B - Permutation Check

$A$をソートしてあげて(1..=N)と一致するかを調べれば良いです．

b.rs

#![allow(unused_imports)]
#![allow(non_snake_case)]
use cmp::{max, min, Reverse};
use proconio::{fastout, input, marker::*};
use std::collections::*;
use std::*;

fn main() {
	input! {
    n:usize,
    mut a:[usize;n]
	}
  a.sort();
  for i in (1..=n) {
      if a[i-1] != i {
        println!("No");
        return;
      }
  }
  println!("Yes");
}

C - POW

$C mod 2$が$0$の時は$A^C,B^C$は必ず正数となります．対して$1$の時には$A^C$,$B^C$のどちらかが負の数になる可能性があることに注意します．
ここで指数は一定なので，上記の内容に注意しつつ$A,B$の比較だけで済むことがわかります．

c.rs

#![allow(unused_imports)]
#![allow(non_snake_case)]
use cmp::{max, min, Reverse};
use proconio::{fastout, input, marker::*};
use std::collections::*;
use std::*;

fn main() {
	input! {
    a:i128,
    b:i128,
    c:i128
  }
  if c%2 == 0 {
    let aa = a.abs();
    let bb = b.abs();
    println!("{}",if aa < bb {'<'}else if aa > bb{'>'}else{'='})
  }else{
    println!("{}",if a < b {'<'}else if a > b{'>'}else{'='})
  }
}

D - Kth Excluded

「小さいものから$K$番目の数字$X$」を探すときは二分探索が有効です．これは「$X$以下の数字が$K$個ある時の最小の$X$」と言い換えられるので，この$X$を二分探索すれば良いです．
Rustにはupper_bound()が存在しないので自作しましょう．

d.rs

#![allow(unused_imports)]
#![allow(non_snake_case)]
use cmp::{max, min, Reverse, Ordering};
use proconio::{fastout, input, marker::*};
use std::collections::*;
use std::*;

pub trait BinarySearch<T> {
    fn lower_bound(&self, x: &T) -> usize;
    fn upper_bound(&self, x: &T) -> usize;
}
impl<T: Ord> BinarySearch<T> for [T] {
    fn lower_bound(&self, key: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();
        while high != low {
            let mid = (low + high) / 2;
            match self[mid].cmp(key) {
                Ordering::Less => {
                    low = mid + 1;
                }
                Ordering::Equal | Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
    fn upper_bound(&self, key: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();
        while high != low {
            let mid = (low + high) / 2;
            match self[mid].cmp(key) {
                Ordering::Less | Ordering::Equal => {
                    low = mid + 1;
                }
                Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
}

fn main() {
	input! {
    n:usize,
    q:usize,
    a:[i128;n],
    k:[i128;q]
	}
  for que in k {
        let mut left:i128 = -1;
        let mut right:i128 = 10000000000000000000 + 1;
        let mut x:i128 = 0;
        let mut mid = 0;
        while right - left > 1 {
            mid = (left + right) / 2;
            x = a.upper_bound(&mid) as i128;
            if (mid - x) < que {
                left = mid;
            }else{
                right = mid;
            }
        }
        println!("{}",right);
  }
}