プログラミング初心者がAtcoderで水色になるまでの話

#はじめに#
こんにちは。Qiita初記事のSotaUNです。先日、ABC179で入<font color = "Cyan">水</font>しました。
![スクリーンショット 2020-09-21 22.29.39.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/732432/c2c4c760-f141-e913-da7d-cfdea62ee6c1.png)
![スクリーンショット 2020-09-21 22.32.17.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/732432/8621c0f7-c964-1b46-0af7-e038f119fb49.png)
ABC178で初めて<font color = "Blue">青</font>パフォを出し、+93した後、ABC179で初<font color = "Yellow">黄</font>パフォを出し、+150しました。
Atcoderを始めてから (というかプログラミングを始めてから)10ヶ月弱の道のりだったので、単純に嬉しいです(^_^)。(ただ、これからパフォが安定するか心配...)
#<font color = "brown"><font color = "brown"><font color = "brown"><font color = "brown">茶</font>色</font></font></font>になるまで#
ここは、<font color = "Gray"><font color = "Gray">灰</font>色</font>や<font color = "brown"><font color = "brown"><font color = "brown">茶</font>色</font></font>を解くだけでも得られることが多いので、1日1問ずつとかを着実に解いて、新しい知識を吸収していけば、自ずと伸びてくるはずです。
私の場合、1ヶ月少しで入<font color = "brown">茶</font>したのですが、問題を解くのをサボっていたら<font color = "Gray">灰</font>落ちしました。コンテストで焦ってペナを連発することもあったので、気分が良くない時はお休みしましょう☕️。気を取り直して問題を解き進めたら、また<font color = "brown"><font color = "brown"><font color = "brown">茶</font>色</font></font>に戻ることができました。
#<font color = "green"><font color = "Green"><font color = "Green">緑</font>色</font></font>になるまで#
入<font color = "Green">緑</font>したのはAtcoderを始めてから半年後くらいです。c++の基礎文法を勉強し始めて、割とすぐに<font color = "brown"><font color = "brown"><font color = "brown">茶</font>色</font></font>にはなったのですが、それからレートが伸び悩み、"**精進**"というものを始めました。
私は、自分の色より**1,2色上**の問題を解き進めるという方法をとりました。2色上の<font color = "Cyan">水</font>色の問題は、解説を見ないと解けなかったのですが、それでも数をある程度こなしていくと、自力で解けるようになっていきました。
<font color = "Gray"><font color = "Gray">灰</font>色</font>,<font color = "brown"><font color = "brown"><font color = "brown">茶</font>色</font></font>とかの問題は、暇なときに埋めれば良いので、まとめて何問も解くというようなことはしていませんでした。
私の場合、ABC164(<font color = "Green">緑</font>になる2回前)にはコンテスト中に<font color = "Cyan">水</font>色が解けるようになりました。
このくらいの時は、まだ本格的なアルゴリズムの勉強はしていなくて、

* BFS
* DFS
* 逆元,繰り返し二乗法
* bit全探索
* 基本的なDP
* 累積和

ぐらいしか知らなかったと思います。最初は難しいですが、とにかくコツコツやるのが大切です。
あとは、問題を解くごとに新しいSTLの機能がどんどん出てくるので、その都度覚えていきました。
また、これらのアルゴリズムの実装やSTLの機能はメモ書きとしてGoogle Keepに残しています。
Google Keepは使いやすくはないのですが、自分のライブラリをどこに保存しようかという時に、手っ取り早かったので、使い始めました。

#<font color = "cyan"><font color = "Cyan">水</font>色</font>になるまで#
入<font color = "Cyan">水</font>したのは<font color = "Green">緑</font>になってから5ヶ月後くらいです。
まず、[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ<font color = "Cyan">水</font>色コーダー！】](https://qiita.com/e869120/items/eb50fdaece12be418faa)は絶対に読むべきです。ここにほぼ全てのことが書いてあります。大変お世話になりました。
私は、<font color = "Green">緑</font>までに覚えていたアルゴリズムに加えて、

* 二分探索
* いろんなDP
* ダイクストラ
* ワーシャルフロイド
* クラスカル
* Union-Find

を覚えました。
最初はこの量のアルゴリズムを見ておげ!となったのですが、3日に1つとか頑張ってやっていくといつの間にか全部できるようになります。

###グラフ系###
私は結構実装でつまずきました。c++の知識がそもそも少ないのが原因だと思いますが、他の人のソースを半写ししたりして実装しました。自分で書いたソースコードのチェックは、AOJに基本問題が大抵載っているので、そこで行えます。
最近のABCでグラフ系のアルゴリズムを使う機会は少ないと思っているのですが、出たら考察は少なめなので、覚えておくと得します。また、[JOIの過去問](https://joi.goodbaton.com)には最短経路問題とかが結構あるので、練習になります。参考までに、自分が参考にしたサイトを載せておきます。

* [ダイクストラ](http://www.deqnotes.net/acmicpc/dijkstra/)
* [ワーシャルフロイド](https://qiita.com/okaryo/items/8e6cd73f8a676b7a5d75)
* [Union-Find](https://www.slideshare.net/mobile/chokudai/union-find-49066733)
* [クラスカル](https://algo-logic.info/kruskal-mst/)


###数学系###
<font color = "Cyan">水</font>色くらいまでの数学系は、基本高校数学で完結するので、覚えておくことは少ないはずです。
私は、○進ハイスクールで勉強しました。
例えば、組み合わせの考え方などはパターンが決まっているので、二項係数の実装と繰り返し二乗法の実装を覚えた後は、困ることはなくなりました(困ってないはず)。

* LCM,GCD
* 組み合わせ
* 確率
* mod
* 幾何系の基本定理(余弦定理など)

###実装系###
実装系といっても80行くらいで収まるものが<font color = "Cyan">水</font>diff以下の問題には多いと思いますが、

* BFS：queueの扱い方
* 二分探索：イテレータの扱い方
* 再帰：頭が混乱
* dp：遷移式が多い時

などは最初の頃はとても苦労しました。
これらは慣れるしかないと思うので、面倒くさがらずに頑張りましょう(自分自身への戒め)。
dpを使う問題はJOIに結構あるので、是非解いてみてください。

#さいごに#
ここまで読んでくださった方、ありがとうございます。少しでも役に立っていればうれしいです。
最後に、<font color = "red">1日最低1問</font>解くことが大切です。時間がある時は<font color = "Cyan">水</font>diff以上とか、時間がない時は<font color = "brown">茶</font>diffとか、とにかく1日1問といてください!!!
[AtCoder Problems](https://kenkoooo.com/atcoder/#/table/https://kenkoooo.com/atcoder/#/table/)のuser pageには連続何ACしているかのカウントがあり、モチベになります。まとまった時間がある時には、バーチャルコンテストをAtcoder Problemsで開いたり、Atcoderの過去のコンテストでバーチャル参加をするのもおすすめです。
次は、<font color = "blue"><font color = "Blue">青</font>色</font>になるまでをかけるように、頑張ります!