はい!今やってます!

Work Pertly, Live Idly

競プロやっていき

main

fn main() {
  println!("Please input.");
  let input = read_vec::<usize>();
  plrintln!("{:?}", input)
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
      .map(|e| e.parse().ok().unwrap()).collect()
}

メソッドやアイデア

cmp::min(1, 2) // 小さい方
hoge.abs() // 絶対値
lower_bound

※A1,A2,...,ANA1,A2,...,AN の中で VV より低い値が何個あるかを O(log2N)で求めてくれる

基礎

コンピューターが計算できるのは1秒間に108 ~ 109 なので、2億 ~ 10億通りの探索を超える場合は別の方法を検討

計算量

logn < √n < n < nlogn < n^2 < 2^n < n!

アルゴリズム12選

全探索(bit 全探索、順列全探索を含む)

たのしい探索アルゴリズムの世界【前編:全探索、bit全探索から半分全列挙まで】 - Qiita

  • すでにわかっているものを探索しない
  • 探索の通り数を絞り込む
  • 別の視点から全探索

深さ優先探索(DFS) ※再帰関数を用いた全探索

幅優先探索(BFS)

二分探索

たのしい探索アルゴリズムの世界【前編:全探索、bit全探索から半分全列挙まで】 - Qiita

動的計画法(bitDP などを含む)

ダイクストラ法(最短経路問題)

ワーシャルフロイド法(最短経路問題)

クラスカル法(最小全域木問題)

高速な素数判定法

べき乗を高速に計算するアルゴリズム

逆元を計算するアルゴリズム

累積和

データ構造(3 個)

グラフ(グラフ理論

Union-Find