3年間でAtCoder Rateが4桁になった話

はじめに

こんにちは，Basinです。
もともとには入緑記事を書きたかったですけど，もう一年経てたのでちょっと上がっているから
今日は私が競プロ始めた以来，3年間を使ってレートが4桁になった話をしようと思います。

(今の)レーティング

最近はいろいろ精進不足で冷えていましたが，，

精進記録

ここまでの経緯

競プロやってはじまったきっかけ

大学の先生が雑にICPCの宣伝が来て，参加したいので競プロについて何かやった方がいいかなって思いながら競プロ始めました。
あの時大学で習ったプログラミング言語はProcessingのJavaしかなかったです。Processingで競プロが使えないですし，Javaでのオブジェクト指向プログラミングもわからない時期でしたので独学でPythonを学びつつ競プロ始めました。

入茶まで

最初にはPythonの本を読みながら進もうと思いましたが，標準入出力が終わったら全く競プロと関係ない話(ファイル処理など)だなっと思ってやめました。
Processingを学んだことだあるので，ifとfor文などにはググって，その書き方だけを覚えました。そしてその時期では，よく他人のコードを読みながら，「みんなこう書くんだ」という習いも行いました。
大体勉強とともにコンテストも出たりしました。最初にはこのコンテストでしたかね。今と比べると結構簡単なので簡単にコンテスト中にAB通しました。しかし，C問題で用いられるUnion-Findにはあのとき何も知らず(そもそもグラフとは何かも知らない)くらいに80分間で結構頑張って書いてみました。
そして過去問勉強の方には，基本的にはABCのABかつ灰色問題を埋めようと思いつつ，頑張って文法も習いながら3ヶ月弱でできました。この時点ではすでに300当たりになって，400くらいには行けないときでした。
そこで特にやらかしたのはTLEでした。私はあのとき，シミュレーションを模倣することを目指して，計算量の話は一切わからなかったです。なので普通に自信満々で5重ループとかも書きました(これはよくないですね)。
そこで，毎回コンテストで解けない部分を事後に解説を読んで，計算量という言葉を認識でき，そして特にリストを集合にすることで基本には間に合うようにできることが分かったのでABC200で入茶。(C問題の提出結果を振り返り見てみるとあのときまだdefaultdictなどの話が分からなさそうでした)

入茶からやる気喪失まで

入茶した後にも健常にC問題を埋めながら精進をしばらくしました。
しかし，550あたりに進んでいたところ，「できることはできる，できないことはできない」と，思い始めました。つまり，毎回のパフォはほぼほぼ固定されていて，レートの増減も1桁の場合が多かったです。かつ，C問題やD問題あたりにはわからないものがよく出てたりしてて，かつ現実的にゼミ配属などにもかかわっていてやる気は喪失しました。

復帰してから入緑へ

復帰する理由も最初とほぼ同じくて，去年のICPCを参加して，先輩が来年度で学年によって引退されることがわかって，そろそろ自分が頑張らないとここでお終いになることがわかりました。
そこで本格的に数学やアルゴリズムを勉強しました。最初にはアルゴリズム×数学という本をよんでいました。E8さんの著書であり，結構やさしい数学から競プロの難しい問題まで紹介されました。一ステップずつ読みながら，演習問題解いたりしていい勉強になりました。
その本を読み終わったところ，ある程度のアルゴリズム(にぶたん，グラフ基礎，DP基礎，素因数分解やユークリッド互除法など)を身に付いていました。
また，その本を読みながら，結構レートもいい感じに増えて，最後には700台を突破しました。
私はC++をしっかり学んでいなかったので，C++だけを記載している本を買うと不安になるので次の本は鹿本にしました。この本の練習問題は前より結構幅広く，難しい問題もいっぱいありました。特に前の本と被ったりするところもありますが，より練習問題の方に集中しました(今考えるところ解説ACが多かったです。。)。その間に入緑して，また茶色に戻ってから完全に入緑できました。

4桁になるまで

鹿本が読み終わったところ，900台にすら入っていなかったです。そこでコツコツ過去問勉強をしながら，鉄則本が出版されました。鉄則本では，各節の前半はやさしい内容を扱い，後半の方は結構発展的な話であったというイメージでしたが，1章ずつ読みながら精進できました。
そこでようやく900台に入りましたが，とても不安定でした。また，「ダブリング」の節にたどったところにはやること本当にわからなさ過ぎて一時放置しました。ここまでにはおそらく今年の9月の頭くらいでした。
次には，Xで宣伝された「精進しないとBANされるサーバー」に入りました。そこで，毎日自分のレートより高い問題を一問解かないといけないという設定なので，毎日頑張って新しい知識を勉強しました。これは2週間で過ごしました。そこで1日少なく1問といっても，緑，水，青diffの問題をたくさん解いてみました。解説ACが多かったですけど学びもありつつ，ある程度「こういう問題だったらこういう方法でいい」というようなことがだいぶわかりました。
そして鉄則本を再開してみました，今回はヒューリスティックの章を抜けて無事で最後まで読みました。そして10月になったらコンテストで水色diff問題を解いて4桁に上がりました。

さらに今まで

4桁になった回には，青diffに近いほどレートを取れたので結構増えました。また，次の回にもたくさん増えて1100台に入りました。しかし，その後私は土日の時間を取るのが急に難しくなり，何週間にコンテストですら出れませんでした。
また，その同時に精進もさぼって，そして先週はARCにギャンブルして負けたので，今はまた1000台に戻りました。

全体的なまとめ

この三年間，いろいろな方法を試して，精進しましたが，一番役に立つを感じられたのは，

• アルゴリズムの本や，ネット記事で必要なアルゴリズムを勉強する
• コンテストでできていなかった問題を，解説ACでもいいので解いてみる
  ことでした。
  また，以下のアルゴリズムやデータ構造を学びました。(時期とは，そのアルゴリズムやデータを学んでいるときの色です。)

アルゴリズム	時期	備考
二分探索	灰色
尺取り法	茶色
半分全列挙	茶色	今でも使い場合がわからなかったり
ユークリッド互除法	灰色
(素)因数分解	灰色
エラストテネスの篩	灰色
ソート	灰色
DFS	茶色
BFS	茶色
Dijkstra	茶色	完全に理解したのは緑になった
DP	茶色	まだたくさんの形で理解できていない
Union-Find	茶色	原理は理解できていない
メモ化	緑色
累積和	茶色
スターク&キュー	茶色
セグメント木	緑色	使うことだけができる
フロー	緑色	使うことだけができる
ビット全探索	茶色
ハッシュ	まだ
BIT	まだ

最後に ~入緑を目指している人へ~

最近のABCでは，決して私が入茶や入緑の時代と違うとわかります。今では，そもそもBFSやDFSが灰色diffだったり，知らないと本当に進まないところです。この辺については，先が話したように，わからないアルゴリズムが出たらググりましょう。1回だけ調べると次回でも書けないだろうと思いますが，とりあえずそのアルゴリズムは何をやっているかを分かっておくといいかなと思います。
また，さらに緑へ行くのは，茶diff問題を安定に解けることが大事です。茶色問題は灰色問題と比べて，新しいアルゴリズムはほぼほぼないと思いますが，応用的にはより高めて求める感じです。その辺については，本と読むかコンテストの直後にもう一問に粘着すればどんどん行けると思います！止まっているのはしばらくだけです！