競プロ典型90問をRustで解いていこう（準備）0日目
はじめに
Rustで競技プログラミングをやってみたのですが、これが結構面白かったので飽きるまでとりあえず続けてみようと思います。 情報系の大学院を出たくせにお前そんなことも知らんのかってのを少しでも減らそうと考えてのことです。
単位や卒業のために必要にかられて、ダイクストラ法を使って宅配時の最適経路をGoogle Map上にピン刺しするのとか 強化学習で簡単な対人ゲーム上の人間っぽい動きを実装したりしてきたのですが、記憶は遥か遠くです。
モチベーションとしては、ソートや二分木の実装も怪しいんじゃないかと思い学び直しを敢行しようと思います。
あと、院生の頃神保町の古本屋で見つけて確保しておいた「アルゴリズム設計マニュアル 上下」も読めるようになると良いなぁという気持ちも少しあります。
アルゴリズム設計マニュアル 上 平田 富夫 https://www.amazon.co.jp/dp/4621085107/ref=cm_sw_r_tw_dp_KN7RMT7MDX4AR5WBJZ1J @amazonJPより
「プログラマ必携」と帯には書かれており、中身パラパラと見て良いね！ってなり買ったものの、本棚の肥やしになっている本です。 上下巻で確か6500円ぐらいだったのですが、面接で交通費が多めに出たので「あぶく銭があるぞ！何か買うぞ！」とウキウキしながら買った記憶があります。
森見登美彦先生も言うてましたが、本棚には「本棚というものは、自分が読んだ本、読んでいる本、近いうちに読む本、いつの日か読む本、いつの日か読めるようになることを信じたい本、いつの日か読めるようになるなら「我が人生に悔いなし」といえる本の集合体」という一文がありますが、私の本棚にもいつの日か読めるようになることを信じたい本が沢山積まれています。
競プロ典型90問
様々なタイプの問題が90問あるようで、まずは気長に解いていこうと考えています。
その問題の難易度表が有志によってまとめられており、解くためのアルゴリズムが一覧になっています。 聞いたこと無いようなアルゴリズム名もあり、さながらアルゴリズムカタログのような様相です。
解いていく順番
1日目～90日目まですでに公開されておりかつ、難易度も一覧化されていました。 非常に悩ましいのが、1日目から順番にといていくと、難易度はバラけるものの出鼻をくじきそうで、 難易度順に並べてやると後半が辛そうだなと言う気持ちもあります。
とりあえず、難易度順に並べたので上から埋めるように解いていくことを目標にやりましょう。 （できるかなぁ…）
| No | 出題日 | 分野 | 実際難易度 | 解いたgithub |
|---|---|---|---|---|
| 4 | 4/2 | 適切な前処理 | ★2 | |
| 10 | 4/9 | 累積和 | ★2 | |
| 16 | 4/16 | 工夫した全探索 | ★3 | |
| 22 | 4/23 | 最大公約数 | ★2 | |
| 24 | 4/26 | パリティ | ★2 | |
| 27 | 4/29 | map | ★2 | |
| 33 | 5/6 | コーナーケース | ★2 | |
| 38 | 5/12 | オーバーフロー | ★3 | |
| 61 | 6/8 | deque | ★2 | |
| 78 | 6/28 | グラフの基礎 | ★2 | |
| 14 | 4/14 | 貪欲法 | ★3 | |
| 20 | 4/21 | 誤差 | ★3 | |
| 46 | 5/21 | mod ごとに考える | ★3 | |
| 50 | 5/26 | 動的計画法 | ★3 | |
| 52 | 5/28 | 因数分解 | ★3 | |
| 55 | 6/1 | 全探索 | ★2 | |
| 67 | 6/15 | N 進数展開 | ★2 | |
| 2 | 3/31 | bit 全探索 | ★3 | |
| 7 | 4/6 | 二分探索 | ★3 | |
| 18 | 4/19 | 三角関数 | ★3 | |
| 32 | 5/5 | 順列全探索 | ★3 | |
| 44 | 5/19 | 見かけ上の位置 | ★3 | |
| 48 | 5/24 | 上界を見積もる | ★3 | |
| 69 | 6/17 | 繰り返し二乗法 | ★3 | |
| 75 | 6/24 | 素因数分解 | ★3 | |
| 76 | 6/25 | 円環 | ★3 | |
| 79 | 6/29 | 操作順序によらない | ★3 | |
| 82 | 7/2 | 部分問題に分解 | ★3 | |
| 84 | 7/5 | ランレングス圧縮 | ★3 | |
| 12 | 4/12 | Union-Find | ★4 4 | |
| 58 | 6/4 | 周期性 | ★4 | |
| 64 | 6/11 | 階差を考える | ★3 | |
| 70 | 6/18 | x, y 独立に考える | ★4 | |
| 85 | 7/6 | 約数の個数 | ★4 | |
| 1 | 3/30 | 二分探索 | ★4 | |
| 3 | 4/1 | DFS／木の直径 | ★4 | |
| 8 | 4/7 | 状態 DP | ★4 | |
| 13 | 4/13 | ダイクストラ法 | ★5 | |
| 26 | 4/28 | 二部グラフ | ★4 | |
| 28 | 4/30 | 二次元いもす法 | ★4 | |
| 30 | 5/3 | 約数列挙 | ★5 | |
| 34 | 5/7 | しゃくとり法 | ★4 | |
| 36 | 5/10 | 45 度回転 | ★5 | |
| 42 | 5/17 | 倍数の性質 | ★4 | |
| 63 | 6/10 | 変な制約に着目 | ★4 | |
| 43 | 5/18 | 拡張ダイクストラ | ★4 | |
| 56 | 6/2 | DP 復元 | ★5 | |
| 66 | 6/14 | 期待値の線形性 | ★5 | |
| 72 | 6/21 | バックトラック | ★4 | |
| 6 | 4/5 | 辞書順貪欲 | ★5 | |
| 21 | 4/22 | 強連結成分分解 | ★5 | |
| 29 | 5/1 | 遅延評価セグ木 | ★5 | |
| 37 | 5/11 | セグメント木 | ★5 | |
| 39 | 5/13 | 主客転倒 | ★5 | |
| 51 | 5/27 | 半分全列挙 | ★5 | |
| 60 | 6/7 | 最長増加部分列 | ★5 | |
| 68 | 6/16 | クエリ先読み | ★5 | |
| 74 | 6/23 | 不変量 | ★6 | |
| 81 | 7/1 | 二次元累積和 | ★5 | |
| 86 | 7/7 | bit ごとに考える | ★5 | |
| 87 | 7/8 | ワーシャルフロイド | ★5 | |
| 11 | 4/10 | DP | ★6 | |
| 54 | 5/31 | グラフの辺を削減 | ★6 | |
| 62 | 6/9 | 後ろから考える | ★6 | |
| 80 | 6/30 | 包除原理 | ★6 | |
| 9 | 4/8 | 偏角ソート | ★6 | |
| 15 | 4/15 | 調和級数 | ★6 | |
| 17 | 4/17 | BIT | ★7 | |
| 19 | 4/20 | 区間 DP | ★6 | |
| 25 | 4/27 | 再帰関数の全探索 | ★7 | |
| 31 | 5/4 | Grundy 数 | ★6 | |
| 45 | 5/20 | ビット DP | ★6 | |
| 73 | 6/22 | 木 DP | ★5 | |
| 77 | 6/26 | 二部マッチング | ★7 | |
| 88 | 7/9 | 鳩ノ巣原理 | ★6 | |
| 35 | 5/8 | LCA | ★7 | |
| 40 | 5/14 | 燃やす埋める問題 | ★7 | |
| 49 | 5/25 | 最小全域木 | ★6 | |
| 53 | 5/29 | 黄金分割探索 | ★7 | |
| 57 | 6/3 | 行列の掃き出し法 | ★6 | |
| 65 | 6/12 | FFT・畳み込み | ★7 | |
| 71 | 6/19 | トポロジカルソート | ★7 | |
| 83 | 7/3 | 平方分割 | ★6 | |
| 89 | 7/10 | 尺取 + 累積和 + DP | ★7 | |
| 5 | 4/3 | 行列累乗・ダブリング | ★7 | |
| 23 | 4/24 | ビット DP | ★7 | |
| 41 | 5/15 | 凸包 | ★7 | |
| 47 | 5/22 | ローリングハッシュ | ★7 | |
| 59 | 6/5 | bitset | ★7 | |
| 90 | 7/11 | 高速きたまさ法 | ★7 |
まとめ
最近何か作りたいものが思いつかねぇなとなってたのですが、 作りたいものが無いのではなく、作りたいものが作れないんじゃないかと思い至りまして、 ブログのネタにもなるし、趣味と実益を兼ねて良い題材何じゃないかと期待しています。
