🏇

ABC205 write up

3 min read

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

A - kcal

A1ml辺りのカロリーに直してあげて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 20の時は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);
  }
}

Discussion

ログインするとコメントできます