プログラミング未経験者がAtCoder青になった話

#はじめに
最近めっきり寒くなり、家から出たくない日が続きますね...
暖房とかかかっているとますます外に出辛くなってしまう...
さて、Qiitaで初めて記事を投稿するsoraieです。先日のABC186で[AtCoder](https://atcoder.jp/)<font color="blue">青</font>になることができたので記事を投稿することにしました。[Twitter](https://twitter.com/soraie_),[AtCoder](https://atcoder.jp/users/soraie)
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">ついに青になりました！！！やったーーーーーーーーーーーー！！！！！！！！！！！！！！！！！！！！！！！ <a href="https://t.co/7sTjTgPHys">pic.twitter.com/7sTjTgPHys</a></p>&mdash; そらいえ (@soraie_) <a href="https://twitter.com/soraie_/status/1340294336781504513?ref_src=twsrc%5Etfw">December 19, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
レートの遷移はこんな感じです。
<img width="750" alt="graph" src="https://pbs.twimg.com/media/EpmuYS1VEAIdynS?format=jpg&name=large">
5月にプログラミング未経験の状態で競プロを始めてまさか半年でAtCoder青になれるなんて思ってなかったので素直に嬉しいです。
せっかく青になったので、AtCoderを始めたてのころから青になるまでにしてきたことをここに書いておきます。参考になれば僕としてはとても嬉しいです。

#目次
[0. AtCoder(競技プログラミング)を始めたてのころ](#0-AtCoder(競技プログラミング)を始めたてのころ)
[1. 茶色になるまで](#1-茶色になるまで)
[2. 緑色になるまで](#2-緑色になるまで)
[3. 水色になるまで](#3-水色になるまで)
[4. 青色になるまで](#4-青色になるまで)
[5. まとめ](#5-まとめ)
[6. おわりに](#6-おわりに)
[7. 参考サイト一覧](#7-参考サイト一覧)

#0. AtCoder(競技プログラミング)を始めたてのころ
何をすればいいのか全く分からず、とりあえず友達が勧めてくれたC++入門サイト[APG4b](https://atcoder.jp/contests/APG4b)を読んで基本的な文法を身に着けていました。
このころは末尾に`;`をつけるのを忘れたり、

```c++:失敗
if(N = 1)
````

```c++:正解
if(N == 1)
```
のように`=`と`==`の区別もついていませんでした。

#1. <font color="brown">茶色</font>になるまで
ここが一番苦労していたかもしれない。僕は[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】](https://qiita.com/e869120/items/f1c6f98364d1443148b3)にとてもお世話になりました。これに加えて、茶色になるために必要な全探索のスキルについてリンクを貼っておきます。

* [単純な全探索](https://nashidos.hatenablog.com/entry/2019/12/18/090907)
* [bit全探索](https://qiita.com/hareku/items/3d08511eab56a481c7db)
* [順列全探索](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#3-2-%E9%A0%86%E5%88%97%E5%85%A8%E6%8E%A2%E7%B4%A2)

#2. <font color="green">緑色</font>になるまで
茶色になるまでに覚えた探索アルゴリズムに加えて

* DFS([前編](https://qiita.com/drken/items/4a7869c5e304883f539b),[後編](https://qiita.com/drken/items/a803d4fc4a727e02f7ba))
* [BFS](https://qiita.com/drken/items/996d80bcae64649a6580)

を履修しました。
この他にもこれに加えて蟻本も買いました。蟻本は色々なアルゴリズムが分かりやすく解説されており、買っておいたほうがいいと思います。

#3. <font color="cyan">水色</font>になるまで
[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](https://qiita.com/e869120/items/eb50fdaece12be418faa)が参考になりました。
また、これは完全に自由なのですがこのころにもう一つ別の言語を習得しておくと問題が解きやすくなるかもしれません。
例えば、僕はC++を使っていたのですが、気を付けないとオーバーフロー[^1]してしまう問題や、なんとなくオーバーフローが怖い問題([ABC180D](https://atcoder.jp/contests/abc180/tasks/abc180_d),[ABC185C](https://atcoder.jp/contests/abc185/tasks/abc185_c)など)が来た時に大きな数を扱えるPyhtonを履修したことで安全に問題が解けるようになりました。
また、逆にPythonを使っている人が実行速度が速いC++を履修しておくことで、助かることがあるかもしれません。

#4. <font color="blue">青色</font>になるまで
このころに[セグ木や遅延セグ木](https://algo-logic.info/segment-tree/#)を履修しました。水色でセグ木は早いという意見もあるようですが、ここ最近セグ木を使う問題が結構出ています。履修しておいて損はないと思います。
<details><summary>例題</summary><div>

* [ABC186F](https://atcoder.jp/contests/abc186/tasks/abc186_f)
* [ABC185F](https://atcoder.jp/contests/abc185/tasks/abc185_f)
* [ABC179F](https://atcoder.jp/contests/abc179/tasks/abc179_f)
* [ABC177F](https://atcoder.jp/contests/abc177/tasks/abc177_f)
* [ABL001D](https://atcoder.jp/contests/abl/tasks/abl_d)
* [ABL001E](https://atcoder.jp/contests/abl/tasks/abl_e)
</div></details>

また、早解きができると同じ得点でも大幅にパフォーマンスが上がるので早解きができるようになりましょう。
そのために必要なのは

* 典型問題に一早く気づき、対処すること
* コードをバグらせないこと
* 問題を必ずしも前から順番に見ていかない
* タイピング速度を上げること

です。下にそれぞれの具体的な説明をします。
##典型問題に一早く気づき、対処する
典型問題はすぐに気づかないと多くの人に抜かされてしまいます。
たとえ気づいたとしても解くのが遅ければ多くの人に抜かされてしまいます。
典型問題をすぐに解けるようにするためには

* 問題をたくさん解き、問題に慣れる
* ライブラリを整備しておく

ことが大切です。

##コードをバグらせない
[実装力で戦える！　～競プロにおける実装テクニック14選～](https://qiita.com/e869120/items/920a6e63435bf6efe539)が参考になります。コードをバグらせないで書くことでバグをとる時間を減らすことができます。

##問題を必ずしも前から順番に見ていかない
これは結構勇気がいるのですが、解けない問題、あるいは実装がとてもめんどくさそうな問題があった場合は思い切ってその問題を飛ばし、別の問題を見て見ることをお勧めします。
コンテストによっては難易度が逆転していることもありえます。
難易度が逆転しているコンテストの例

* [ABC155](https://atcoder.jp/contests/abc155)
* [ABC179](https://atcoder.jp/contests/abc179)
* [ABC185](https://atcoder.jp/contests/abc185)

##タイピング速度を上げる
タイピング速度を上げることで実装が早くなります。タイピングの練習ができるサイトを載せておきます。

* [寿司打](http://typingx0.net/sushida/)
* [Easyタイピング](http://typingx0.net/easy/)
* [Typing War](http://typingwar.trap.games/)

まあこんなことを言っていますが僕はタイピングが結構遅く、180key/minが精いっぱいです...

#5. まとめ
ここまで各色になるまでに必要なアルゴリズムを挙げてきました。これらは、覚えるだけでなく使えるようにならなければいけません。そのために毎日精進[^2]し、できるだけたくさんコンテストに出て、実践をすることが大切なのです。また、AtCoderだけでなく

* [Codeforces](https://codeforces.com/)
* [Topcoder](https://www.topcoder.com/)
* [Yukicoder](https://yukicoder.me/)
* [HackerRank](https://www.hackerrank.com/dashboard)
* [CodinGame](https://www.codingame.com/home)
* [AOJ](https://onlinejudge.u-aizu.ac.jp/home)

などの他サイトも利用してみるともっと実力が付くと思います。

#6. おわりに
最後まで記事を読んでくれてありがとうございました！大事なのはアルゴリズムを覚えるだけではなく<strong><font color="red">使えるようになる</font></strong>ことです。たくさん問題を解いてたくさんコンテストに出れば、その分実力が付きます。コンテストでレートが下がっても気を落とさず頑張ることが大切です。
これからも記事を書くかもしれないので、その時はよろしくお願いします。
<font color="yellow">黄色</font>目指して頑張るぞー！では、よい競プロライフを！

#7. 参考サイト一覧
* レッドコーダーが教える、競プロ・AtCoder上達のガイドライン @e869120 <br>
[【初級編：競プロを始めよう】](https://qiita.com/e869120/items/f1c6f98364d1443148b3)[【中級編：目指せ水色コーダー！】](https://qiita.com/e869120/items/eb50fdaece12be418faa)
* [たのしい探索アルゴリズムの世界](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#3-2-%E9%A0%86%E5%88%97%E5%85%A8%E6%8E%A2%E7%B4%A2) @e869120 
* [実装力で戦える！　～競プロにおける実装テクニック14選～](https://qiita.com/e869120/items/920a6e63435bf6efe539) @e869120 
* [Pythonで単純な全探索を実装してみる](https://nashidos.hatenablog.com/entry/2019/12/18/090907) [@nashidos](https://nashidos.hatenablog.com/about)
* [bit全探索について簡単にまとめる](https://qiita.com/hareku/items/3d08511eab56a481c7db) @hareku
* [DFS (深さ優先探索) 超入門！](https://qiita.com/drken/items/4a7869c5e304883f539b) @drken 
* [BFS (幅優先探索) 超入門！](https://qiita.com/drken/items/996d80bcae64649a6580) @drken 
* [セグメント木を徹底解説！0から遅延評価やモノイドまで](https://algo-logic.info/segment-tree/#)


[^1]: 数値型が表現可能な値の上限を超えること
[^2]: 問題を解くこと