初めに
今年も年の瀬。
振り返ってみると緑になかなか届かない（というより茶色から抜け出せない）一年でした
初心に帰って
他の人の上達具合を読んでいると下記のリンク（水色だけど）に必要条件のようなものが書いてあった
https://qiita.com/e869120/items/eb50fdaece12be418faa#0-%E3%81%AF%E3%81%98%E3%82%81%E3%81%AB
現在自分がどのくらいの状態なのかを判断するため
この記事の2-2-1～3あたりを身に着けているかどうか確認する。
なお、似たようなことをrustでちゃんと書いている人がいる
https://qiita.com/hossie/items/e170eb80f48cdb4f6b51
ふむふむという感じ。例を書いたり自分が知らんかったりするものは使わせてもらう。
#対応に関して
標準ライブラリ
以下が必要なライブラリは以下らしい
| C | rust | 把握 |
|---|---|---|
| abs | (-1).abs() | ○ |
| sin/cos/tan | (PI / 2.0).sin() | ○ |
| string | string、Chars | o、proconioの型で受ける |
| min/max | 1.0.min(2.0) | ○ |
| swap | v.swap(0, 2) | ○、index 指定であることに注意 |
| __gcd | 要自作 | ○ |
| rand | use rand::prelude::*; | ○ |
| clock | std::time | × |
| reverse | ? | 要自作？ |
| sort | v.sort() | ○ |
| vector | vec![] | o |
| stack | vec![] | o |
| queue | VecDeque | o |
| priority_queue | BinaryHeap | o |
| map | HashMap, BTreeMap | o |
| lower_bound | superslice::Ext | × |
| set | HashSet, BTreeSet | o |
| pair | (i32,i64) | o |
| tuple | (i32,i64) | o |
| assert | assert_eq! | o |
| count | v.iter().filter(|&&x| x == 1).count() | x |
| find | a.iter().find(|&&x| x == 2 | o |
| next_permutation | superslice::Ext | x |
| __builtin_popcount | ? | x |
| bitset | bitset_fixed::BitSet | x |
後半は全然。
典型的なアルゴリズム
| アルゴリズム | rust | 把握 |
|---|---|---|
| 全探索 | 色々 | o |
| 二分探索 | v.binary_search(&2) | o |
| 深さ優先探索 (DFS) | 自作 | o |
| 幅優先探索 (BFS) | 自作 | o |
| 動的計画法 (DP) | 自作 | o |
| ダイクストラ法 | ？ | x |
| ワーシャルフロイド法 | ？ | x |
| クラスカル法 | ？ | x |
| 高速な素数判定法 | 自作（エラストテネス） | o |
| べき乗を高速に計算する手法 | 自作 | o |
| 逆元を計算する手法 | 自作 | o |
| 累積和 | 自作 | o |
こっちは最短経路だけ完全に×
データ構造
| アルゴリズム | rust | 把握 |
|---|---|---|
| グラフ | 自作 | o |
| 木 | ？ | x |
| unionfind | 自作 | o |
こんな感じ。木はあんまり見ない気もする
とはいえ結構丸がついてる感じ。とりあえずreverseあたりの実装と最短経路は勉強していきたい。
来年は緑になってるといいなあ