【Atcoder】入緑したのでここまでの勉強をまとめてみた【Python】

入緑しました〜！
最近のもので描かれてる記事もないのと、久々に文字として何か書かないとまずいなと思ってつらつら書いておきます。
![スクリーンショット 2022-02-06 14.43.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/384600/bf5e94d6-36ec-086d-322b-28b3d8a55502.png)

# 筆者のスタート地点
アルゴリズムに関する知識は皆無。（二分探索や、累積和などすら知りませんでした）
それ以外仕事では主にフロントエンドの実装を行っておりSwiftが最近はメインです。学生時代はReactNativeを使ってインターンに参加したりをしていました。
そのため、Atcoderの計算量を意識することなく、愚直に計算するA,Bぐらいは書けるレベルのスタートになります。
C++が競プロではスタンダートですが、業務との兼ね合いもあるし、これ以上学ぶ言語も増やしたくなかったのと余程のことがない限り今はPythonで書いてPypyで出せば通るので少し馴染みがあったPythonを選択しました。現時点でPythonで困ったことといえば、解説記事を探すのがなかなかピンポイントではないことですかね。ただ、一つの言語学べば何をしようとしてるか読み取ることぐらいはできますのでなんとかなります。

経歴とか、学生時代の話とかはブログに書いたりしているので、気になる方はこちらも見てみてください。
https://kaleido01.com/

# 入緑までにかかった時間
結論だけ知りたい方もいるかと思うので先にまとめておきます。
アルゴリズム勉強,実践演習期間(約3~4ヶ月）
1日の勉強時間に換算するとおそらく2~3時間。難易度にもよりますが5~10ACぐらいです。1日アルゴリズムを一つ学んで、適当に１コンテスト分(もしくは該当アルゴリズムを利用した問題に絞って）やるイメージです.

コンテスト参加回数　計１８回
ABC 14回
ARC ４回


# 勉強の開始日, 初コンテスト(2020年11月11日）

遡る限り、この日にACを始めて出していたのでこの日を最初の日ということにします。
この時点でABCのA問題、B問題は楽々解けるレベル。C問題は計算量を意識しない数学的な問題でない限り解くことはできず、TLE(時間超過）がほとんどでした。
Dは全くわからず。

https://atcoder.jp/contests/abc183/submissions?f.User=kaleido&page=2
ちなみに初コンテストはA問題、B問題で終わりました。確か今でも記憶に残っていますが、Cは移動順番を全探索して調べればいいだけの問題だったはずですが、当時はPythonにそこまで詳しいわけではなく（今でも大したことないですが）順列の全パターンをどうやって導出するかわからずに詰んでいたのを覚えています。

というわけで呆気なく初めてのAtcoderで散ったわけですが、ここからは具体的にどんな勉強をしていったか書いていこうと思います。

# 典型アルゴリズムを学ぶ(2020年11月11日~）
とりあえず何から始めようか悩んでいましたが、競プロもだいぶ進んできていて、勉強のための資料も結構出回っていました。私は蟻本と呼ばれる本を買って頑張ろうと思っていましたが、難易度が高く挫折。


そこで一番おすすめがまずはこの記事通りに読み進めていくことです。
https://qiita.com/e869120/items/f1c6f98364d1443148b3
現役のレッドコーダー（世界でも数十人しかいない）のE869120さんが書いている記事で、Atcoderで問題を解くために学ぶべきアルゴリズムと問題たちをまとめてくれた記事になります。

やっぱり自分が何を学ぶべきかよくわからないままスタートするより、全体像を知ってから勉強を始める方が効率がいいのと、ABCのD問題までは考察でどうのこうのよりもアルゴリズムを知らないと手詰まりになることが多いです（計算量を削減するようなアルゴリズムを学ばずその場で思いつくのはほぼ不可能だと思います）
例えば累積和は理解するのにそんなに時間はかからないですが、知らない人がこれをいきなり思いついて使えるかというと一部の天才型を除いて無理でしょう
凡人はまずは使える道具をテーブルに広げてそこを基準にどれを適用できるか考える方が得策だと思います。

今の所、アルゴリズムの勉強に関しては、後述する典型９０の問題と合わせて緑〜青色（黄色までもおそらく）なら本当に完結していると思いますので信じて大丈夫です。

# 1年間のブランク（放置期間）
レート見たらわかるかと思いますが、実は１年間丸々ブランクがあります（この間競プロの勉強はしていないです）
理由は業務が忙しかった(言い訳)のと、
https://atcoder.jp/contests/abc191/tasks/abc191_c
この問題があまりにも難しく萎えてしまった（結局緑diffの上位）ので一旦身を引きました。
今思えば緑diff上位なので解けなくても全く問題ないのですが、これだと実質A、Bしか解けてないことになり、大きくこの時レートを落としてしまったのが結構効きました。
この問題は実装というよりは考察がかなり重めでじゃあこうすればできるからやってみてと言われれば実装自体はとても軽いものです。こういうのは普通ARCに出るのですが、時たまABCにも出てくるため、解けなかった時のダメージはでかいです。

https://atcoder.jp/contests/abc184/tasks/abc184_c
この時期に出ていたこの問題もそうですね。
D問題までは典型アルゴリズムを使えば少しの考察で解ける問題と、典型アルゴリズムというよりは数学的知識や、考察が重めの問題（そこに気付けるかどうか）で勝負が決まる問題に分かれます。

勉強しやすいのは当然前者のほうであるため、後者のような問題が出てきたときはあまり気負わずに次の時を待ちましょう。実際一年のブランクあけて参加してからの中でCが解けなかったことはないです。緑まではDが５割ぐらい解ければ問題ないです。私も時々緑上位のDは解けないです。。

逆に学びとして、考察重めの問題は解けた時のレーティングの盛りも大きく緑に到達した時は
こちらのほぼ青問題を解けたおかげで爆盛りできたのもあります。実装自体はすごい簡単なのと、私の提出を見てもらえればわかるとおりDの提出時間に対してEは15分程度の考察で終わっています。

というわけで何が言いたいかというと、Atcoderは一問解けたか、解けなかったかでだいぶレーティングが変動するためC, Dでうろついている時はこの変動を見る機会も多いのであんまり気にしないようにして手数を増やそうねということです。


# 典型90問の登場
こちらは昨年に先ほど紹介した記事のE869120さんが出している、その名の通り典型的な解法を寄せ集めたものになります。
https://atcoder.jp/contests/typical90
今年になって勉強を復活して、こちらのコンテンツが出てたので、とりあえず⭐️５までは埋めて、６をやったりやらなかったりです。実際は⭐️４までで緑は足ります。
先ほどの100問を解いた後の復習としても優秀です。ちなみに私は最初の1問目からわからず。笑

注意としては先に紹介したアルゴリズム全体を知って、その上でそれらを使った問題を解けますか？というのがメインになりますので、まずアルゴリズム！という方は先に紹介したアルゴリズム勉強->演習というような手順をお勧めします。


# アルゴリズムを学んだらどう適用するかのパターンを知る
勉強の段階には２ステップあると思っていて、
- 問題で使われているアルゴリズムを学ぶ
- 次回以降同じアルゴリズムを使って解く問題対してどう落とし込むかを学ぶ

一つ目はそのままアルゴリズムを学ぶだけです。
二つ目は残念ながらそのまま学ぶことは難しくなぜなら、特定のアルゴリズムを使うとわかった上で問題を解き始めてしまうと、それを使うことがわかっているため意味がありません。そのため、どんな解法を使って解くかをわからない状態で新しい問題に触る必要があるため、直接的にこのアルゴリズムを強化したいと思ってできるものではないです。

そのためAtcoder Problemsなどを使ってRecommendationされている問題を解くことで思考力を鍛えるのが一番いいかなと思います。上記の100問と、典型の⭐️４まで終わった後はこれをやっていました。基本的にわからなかった問題は、こういうルートでこの解放まで落とし込むのかという部分をメモしておくことで本番中に見返せるようにしています。

例えば、逆順で見ていくとqueueで処理できないか。とか。
アルゴリズムを適用するまでの過程は慣れるしかないです。と同時に、そんなすぐにできるものでもないので、頑張ってたくさんの問題に触れましょう。

参考までに私が解いた問題数です。

![スクリーンショット 2022-02-06 16.39.46.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/384600/e6f10688-6cab-9b21-8db1-c18a0816d99b.png)

私のIDのkaleidoで検索すればどれを解いたのかもわかるので合わせて参考にしてみてください。
所感ですが、最近の問題はアルゴリズム適用までの考察がだんだん重くなってきているのに対して、最初の方の問題たちは割と考察からアルゴリズムの実装までがスムーズな印象です。
これは、おそらく当時に比べて参加者のレベルも上がってきており単純な問題もなかなか出しづらくなってきてるのだと思います。


# 今後の目標

ひとまずは入水を最低限の目標にして頑張ろうと思います。水色は今までの感覚だと、ABCDの考察をどれだけ早く終えてACできるかのパフォーマンス帯になってくるため、考察からアルゴリズムまでの実装の訓練をさらに問題を解いて早めていけるように頑張りたいですね。そのためには引き出しも多くする必要があるため引き続き、問題を解いていきます。

Twitter、ブログやっていますので気になったかたは是非フォローお願いします。


# その他勉強をする上で特定の問題の解説でお世話になった記事
[けんちょんの競プロ精進記録](https://drken1215.hatenablog.com/)
ブログ以外にもQiitaで各トピックでめちゃくちゃわかりやすい解説を載せてくれてるので、アルゴリズム勉強しているうちに必ず出会うはずです。

[はまやんさん](https://blog.hamayanhamayan.com/)
ABCの比較的中期-初期の問題のユーザー解説としてたびたび出てきます。学び始めると、なぜその答えになった？という疑問が湧いてきますが、本番中にどのような思考ステップでそこにたどり着いたか書いてくれてるのが個人的には好きです。

[かつっぱさん](https://www.youtube.com/channel/UCqqeYOh1gk_TJ16sxazWhUg)
競プロYoutuberの方で最近は主にPythonでABCのリアルタイム実況を上げてくれています。上記を同じ理由でリアルタイムのため、なぜその思考に行き着いたかを言語化してくれるためとてもわかりやすいです。また、競プロ90の解説もPythonで順次載せてくれているため合わせて参考にするといいかなと思います。