0. はじめに
先日のABC286で青レーティングに到達したので、ここまでの進捗メモを兼ねてこれまでやってきたことをまとめてみます。
1. 経歴
- 理系大学出身
- 数学はそれなりに得意
- 開発経験はほぼなし
- アルゴリズムの知識は『数学ガール 乱択アルゴリズム』を読んだくらい
- ちょっとした計算にPythonを使っていた
- アソビ大全のマンカラ最大得点、Muse Dashの理論値、Wordleのソルバー……etc
「Pythonもっと使えるようになりたいなー」「アルゴリズムも学びたいなー」→「競技プログラミングなるものがあるらしい」という流れで始めました。
2. やったこと
アルゴリズム・データ構造を知る
本でまとめて勉強する方が好きなので、ちょうど発売したてだったE869120さんの本『アルゴリズム×数学』と『競技プログラミングの鉄則』で勉強しました。
定番の『蟻本』も買ったものの、こちらは中級の半ばで積んでます。
その他、解説に出てきたものやコミュニティで名前が挙がるものも、解説記事を探しつつ実装を試みたりもしました。（形式的冪級数・ウェーブレット行列など）
スニペット・ライブラリ整備
汎用性の高そうなもの、書くのが面倒そうなもの……etc色々作ってはスニペットに登録しました。
特にC++にあってPythonにないAtCoder Libraryやstd::setの代替物はとりあえず入れておくと幸せになれます。
入れるついでに解説記事と実装を読みながら動作を理解するようにもしました。（完全に理解できないまでも、考え方を一度把握しておくのは大事かなと）
問題演習
AtCoder Problemsが便利すぎる
Boot camp for Beginners
AtCoder Problems右上の"Training"から行けるやつです。
競プロの雰囲気とか基礎とか掴むのにいい感じでした。ただ300問はちょっと多かったかも……？
RecommendationのModerate・Difficult埋め
Userのページにある、レート的にほどよい難易度の問題を提案してくれるやつです。
「1日1問、1時間考えてわからなかったら解説読んでACする」という感じでゆっくり進めてました。
意外と大変だったので、最近は気が向いたときだけ……
しっかり考察力がつく気がします。
あさかつ
毎朝7:30-8:30に開催されているバーチャルコンテストです。灰灰茶緑水青の6問がいい感じにランダムに出題されます。こんな感じ。
朝起きれないことも多いので、後から解いたり解かなかったりですが……
速解き力が鍛えられる気がします。
3. 進捗
問題演習
問題数
もうすぐ1000問に届くくらい。
難易度別
「下から全部埋めよう！」みたいなモチベはあまりないので、灰茶あたりも埋まってません。
青-黄あたりの初見の問題がまだまだ尽きそうにないのはありがたい。
アルゴリズム
習得状況を、名前だけ知ってるようなものも含めて色々書いてみます。勉強中の部分の分類が不適切な可能性がありますが、ご容赦ください。
アルゴリズムを列挙するにあたり、cozy_saunaさんの入青記事・Ryusukeさんの入水記事・いかたこのたこつぼを参考にしました。
×：よくわからん・使いこなせない
△：知ってはいる・資料を見ながらなら使える
○：ライブラリから持ってきて使える
◎：空で書ける
| ◎ ダイクストラ法 | ◎ ワーシャルフロイド法 | ◎ ベルマンフォード法 |
| △ プリム法 | △ クラスカル法 | △ オイラーツアー |
| △ トポロジカルソート | × 強連結成分分解 | △ 最大流・最小カット |
| × 最小費用流 |
| ◎ 幅優先探索 | ◎ 深さ優先探索 | ◎ bit全探索 |
| ◎ 半数全列挙 | ◎ 順列全探索 | ○ 二分探索 |
| △ 三分探索 | × 平方分割 | × 分割統治法 |
| ◎ 1次元 | ◎ 2次元 | △ 最長共通部分列 |
| ◎ 最長増加部分列 | ◎ 区間DP | △ 期待値DP |
| △ 確率DP | ◎ bitDP | × 桁DP |
| × 木DP | × 全方位木DP | △ ダブリング |
| × ゼータ変換 |
| ○ Union Find | × 永続Union Find | ○ Binary Indexed Tree |
| ○ Segment Tree | ×遅延セグ木 | × Wavelet Matrix |
| ◎ 素数判定(試し割り) | ○ 素数判定(ミラー・ラビン) | ◎ 素数列挙(エラトステネス) |
| ◎ 素因数分解(試し割り) | ○ 素因数分解(ポラード・ロー) | ◎ mod演算の累乗・逆元 |
| ◎ ユークリッドの互除法 | × 拡張ユークリッドの互除法 | × モンゴメリ乗算 |
| △ 高速フーリエ変換 | △ 形式的冪級数 | × きたまさ法 |
| △ Bostan-Mori法 | △ Grundy数 | ○ 凸包 |
| △ 編集距離 | △ ローリングハッシュ | × Z-Algorithm |
| × Suffix Array | × Trie木 |
4. 今後の目標
目標
-
黄コーダーになる
直近のABCで黄パフォーマンスも出せてるので、この調子でレートをもりもり上げていきたいです。 - PASTエキスパート
去年の3月に中級を取ったので、次は上級、あわよくばエキスパートまで行きたいです。 - 記事を書く
勉強したことや問題を解いたときの思考の過程を残せるといいなと思ってます。
これからやること
- 典型90
始めてすぐくらいに触れて★5以上がわからず投げてたので、実力ついてきた今改めて触れておきたいです。 - 蟻本の中級～
まだ読んでしかいない部分が多々あるので…… - 青～黄diff埋め
引き続きRecommendationから。特に黄diffを頑張っていきたいなと - numba, numpy, scipy等のライブラリの把握
現在のAtCoderのPyPyでは使えませんが、近々言語アップデートで使えるようになるかもしれない＆普段遣いでも使えるようになりたいので、そろそろ勉強しておきたいなと思ってます。 - ABCに出る
土曜夜9時って配信とかと時間被って参加しづらくない？ - ARCにも出る
adhocな問題も解けるようにしていきたいです - Project Euler
ちょっと気になってます。
5. 最後に
記事の締め方がわかりません！！！！！！！！