AtCoder緑になるまでにやってきたこと
タイトルの通り、AtCoder緑になりました！！！！！！ ということで今回は、(よくある)私が緑色になるまでにやってきたことを書いていきます。 精進量について 私が習得したアルゴリズムなどに触れていく前に、どれだけ精進したかについて書いていきます。 精進量は多くも少なくもないといったものだと思います。 次は精進量の推移についてです。今年に入ってから精進量を一気に増やしました。 今年に入ってからは、ABCのA・B埋めと新しいアルゴリズムの開拓の2つを中心に精進しました。 結果として、ABCのA・B埋めは早解きを安定させた要因の一つになったはず。 開拓したアルゴリズムは直近のコンテストには出てこなかったので今後に期待という感じです。 取り組んできた内容 この部分は所謂、「こんなアルゴリズムを習得した」とか、「このようなテクニックが少し使える」とかを書いていきます。 また、テンプレの作成や特定のアルゴリズムを用いる際に参考にしているサイトも合わせて紹介していきます。 その1. 基本的なものであれば取り扱えるようになったアルゴリズム・テクニック 全探索(DFS・BFS) 順列(next_permutation) STLの一部 最大公約数・最小公倍数・約数列挙 累積和 その2. 理論部分は曖昧だが、何とか取り扱えるアルゴリズム・テクニック DP(ナップザックDP・桁DPを含む) bit全探索 MOD演算(逆元を用いたものも含む) 二項係数(テーブルを事前作成するタイプのもの) ダイクストラ法 ワーシャルフロイド法 Union Find その3. アルゴリズム・テクニック以外で取り組んだ内容 AtCoderの自動提出ツール タイピングの練習 全探索(DFS・BFS) ここで挙げるDFS・BFSを除いた全探索のレベルとしては、 ABC85 C Otoshidama のような問題をスムーズに実装出来る程度です。 DFS・BFSについては他のアルゴリズムと組み合わせて解く高度な問題を除いた基本的な問題を解くことが出来るレベルです。 例 : ARC31 B 埋め立て , ABC160 D Line++ 参考にしている記事 BFS : BFS (幅優先探索) 超入門！
