AtCoder黄色になるまでにやったこととやっていないこと
33歳から競プロを始めた35歳業プロerのks2mです。
2021/2/20にAtCoderで黄色になったので、一度くらいはよくある色変記事を書いてみようと思いました。
水色や青になった時に書かなかった分、長くなります。
遅筆な上、最近時間がなく、黄色になってからこれを書き終えるまで2週間も経ってしまいました。
AtCoderを始めるまで
一応学生時代の数学周りの学力とかの背景から。
高校まで
中学までは、学校の定期テストで、数学はテスト勉強を全くせずにほぼ100点が当たり前なくらいには得意でした。
高校では、学年が上がるごとに明らかにできる度合いが下がっていき、3年でやった気がする極限とか行列とかはあまりまともに理解していなかったと思います。
競プロでよく出てくる場合の数、確率、三角関数の基本などはだいたい高1範囲だったかと思うので（今の高校の内容も同じかは知りませんが）、倍の年齢になった今でもまあなんとかなっています。
正弦定理などといった定理や公式の類は今ではほぼ全く覚えてないですが。
大学入試においては、センター試験の１Ａは概ね100点、２Ｂは60～100点の間くらいで不安定といったレベル感。
東大、東工大とかの数学には全く歯が立たず、他の有名私大になんとか引っかかった感じです。
ここまで、普通の公立学校で習うこと＋受験勉強以外の特別なことは、ほぼ何もしていないと思います。
大学
大学は理工学部の情報系の学科。7割くらいの人は院進するようなところでしたが、自分は目的もなくあと2年も勉強できる気がしなかったので学部卒止まり。
数学は1年の時だけ必修科目にありましたが、もはやなんとか単位は取っただけで、ほぼ何も覚えていません。
同じく1年の必修科目にプログラミングがあり、ここでまず1年間Javaを勉強します。これの成績は良かったです。
他にも情報数学だったか情報理論だったかそんな感じの科目で、進数やXORやModのこと色々（逆元とかも）や誤差のことなどをやった気がします。
（進数くらいだったら高校以下でも出てきていたと思うけど）
あとは2年の必修科目でアルゴリズムとデータ構造がありましたが、こちらは壊滅的でした。
ソート、探索、動的計画法、メモ化再帰といった単語が出てきていたことはなんとなく覚えています。
当時は、フィボナッチ数列を求めるのに何で再帰呼び出ししなければならないんだとか、動的計画法の遷移が中途半端に書かれた表を見せられて「この矢印何？ 何でそことそこを足すの？」ってなったりとかで、さっぱり理解できませんでした。
社会人
とあるIT企業に就職してからも使用言語は主にJava。プログラムを書くことは多い時もあればほぼ皆無な時もありつつ、2019年にAtCoderを始めるまでの期間は10年ほど。
5～6年目くらいの頃に一度、客観的な実力を測れるようなサイトがどこかにないかと思い、その時に見つけたのがpaiza。
Sランク問題の中では最も簡単そうなものだけ2～3問やって、なんとかSランクにはなれました。
それから数年経って再び似たようなサイトを探して、今度はAtCoderにたどり着きました。
結局この時点のスキルセットは、高1レベルくらいの数学力と、大学卒業やいくつかの情報系資格持ち程度の情報科学力と、約10年の業務経験による実装力くらいのものかなといったところです。
とりあえず、やりたいことがわかっているのに文法がわからなくて書けないということはほぼないくらいにはJavaを使い慣れていて、SetやMapは十分使いこなせるくらいではあったと思います。
そして実質緑最下層くらいからのスタート。
AtCoderを始める前からできたor知っていたこと
- if文、for文、while文等の扱い
- List、Set、Mapの扱い
- 割り算以外のMod計算
- BigDecimalの扱い（小数の正確な計算）
- 簡単なグラフの扱い（※隣接リストを作ることが知識ではなく発想だった）
- 二分探索（※実装はとても遅い）
- コンパレータを用いたソート（※実装は遅い）
- 再帰関数（※無限ループ等バグらせまくり）
- XORの基本的な性質
- メモ化再帰（※ほぼ概念としてだけ）
灰～緑色（2019年1月～4月）
2月までは、コンテストに参加するだけの無精進期間。
初めは競プロで役に立つような知識がほとんどないので、C問題があまり難しくないアドホックなら3完できるという感じでした。
参加5回目からレートが頭打ちになってきて、3月からコンテスト参加以外に過去問で精進を始めます。
なお、コンテスト本番については、灰色当初から2021年3月現在に至るまで、参加できるものには全て参加しており、不参加になるのは年数回程度です。
ただし、マラソンは別で、期間の長さに反比例するように参加率が下がっています。（2時間や4時間のものは結構参加するだけはしている気がするが、2週間とかのものは1回くらいしか参加していない）
過去問精進では、ABCのA問題とB問題はやる必要はないと思い、まずはC問題を概ね新しい方から順に埋めていきました。
知らないものはどうしようもないので、長時間自力で考えるようなことは全くせず、5分10分考えてちょっとでも知らなそうな気配を感じたら、すぐさま解説を見ていました。
精進開始から2週間後、2019/3/16のAGC031でDPを使う水diffの問題を通すことができ、早速成果が出てきたかと思いきや、翌週のAGC032では0完灰パフォ、さらに翌日のABC122では2完茶パフォでレートは一気に元に戻り、結果として3週間かけてレートが上がっていない状態。
実際のところこの3週間では1日当たり1.5問程度しか解いておらず、高々30問やったくらいで緑から簡単に上がるわけがないという感じもしますが、初心者的には少なくない問題数なので、なかなか厳しい現実でした。
始めたばかりの一番伸びそうな時期に、3週間勉強してレート上昇ほぼゼロで、この頃が一番辛かったと思います。
結局、AtCoder参加歴2年間全体を通しても、茶色以下のパフォを出したのはこの時の2回だけで、まあ仕方ない事故だったのかなと。
それから精進量を増やし、難しい問題は飛ばしつつABCのC問題を埋めていき、その後はD問題埋めをしようとしていました。（実際は多分そんなに多くは埋まっていない）
4月初めには100AC、4月末には200ACに達していたようです。
同じく4月にはyukicoderにも手を出し始めていました。
こちらはコンテストへの参加のみで、過去問を埋めるようなことは、2021年3月現在でもまだしていません。
そして、2019/5/4のAGC033で、B問題で嘘解法を通し、C問題は木の直径を求めるダブルスイープを自力で発明して通し、黄パフォを出して水色になりました。
水色（2019年5月～10月）
自分が水色になったのと同時に、ABCが4問から6問になり、Rated範囲も拡大されました。
本当に、ちょうどいいタイミングでAtCoderやり始めたなと思います。
多分AtCoder ProblemsやAtCoder Scoresを知ったのが緑後半か水色初めくらいの頃。
AtCoder Problemsを使いながら、引き続き緑時代にやり残したABCのC、D問題を縦に埋めていったり、ARCを横に埋めていったり（大抵は2問目までで終了）、AGCのA問題を埋めていったりということをしつつ、AtCoder Scoresを使いながら300点埋め、400点埋めというやり方もしていました。
過去問をやるときは、やはり大して粘らずに解説ACをすることが多いです。
解説を見るまでの時間は、緑時代より多少長くはなっていたかもしれませんが、まだまだ前提知識が足りていないという意識が強く、考察の進展があまりないような状態で20分以上粘ることはまずなかったと思います。
あと、コンテスト本番については、公式の解説放送を全て見ています。（1.75倍速で）
AtCoder Scoresの精進グラフをよく気にしていて、当時は精進の結果は1ヶ月ほど遅れてレートに反映されてくるように思っていました。
AtCoderを始めた当初は、「水色には絶対なる」、「青はわからない」と思っていましたが、順調に1500近くまでレートが上がってくると、青はまあ行けるだろうという気持ちになってきます。
そして、コンテスト本番と過去問を合わせて月に約100問のペースで解き続け、2019/8/4のABC136で一瞬青に届きました。しかし、その後3ヶ月間1500台に戻ることになります。
AC数としては、この一瞬青タッチ時点で約540問でしたが、ここからAC数の伸びもレート上昇も鈍化していきます。
11月初めに完全に青になった時点で、AtCoderが約700問、yukicoderが約60問といったところです。
9月に2泊3日以上出かける日があり、そこで一度半年続いたStreakを切ったところ、2週間ほど何もしなくなってしまったので、その後は虚無だろうと何だろうと、とりあえずStreakは維持することにしました。
それから2019/10/18に一度yukicoderに気を取られて切ってしまって以来ずっと繋いでおり、2021年3月現在で500日を突破しています。
青色になる頃までに習得orライブラリ整備したもの
- 答えの二分探索（条件を満たす／満たさないの境界を見つける二分探索）
- 繰り返し二乗法（
の累乗計算）
- 二次元累積和
- 階乗を前計算して組合せ
を
で求める
- パスカルの三角形
- エラトステネスの篩
- 座標圧縮
- Nim、Grundy数
- 01BFS
- Binary Indexed Tree（BIT）（※一旦のライブラリ整備だけ）
- セグメント木（※一旦のライブラリ整備だけ）
- 転倒数
- 最長共通部分列（LCS）
- 最長増加部分列（LIS）
- クラスカル法
- トポロジカルソート
- 二部グラフの最大マッチング
セグメント木については、もはやほぼ使うだけの問題は緑diffしかないようですが、自分は水色終盤になってやっと触れ始め、まともに使えるようになったのは完全に青になってからでした。
単語だけはもっと前からちらほら目にしていましたが、実際に使えるようにしていこうとしたきっかけは、2019/9/6のyukicoder contest 222（セグメント木コンテスト）です。
青色（2019年11月～2021年2月）
ここまで来た頃には、黄色到達とアルゴリズム実技検定（PAST）エキスパートが最終目標になっていたと思います。
AtCoder ProblemsにDifficultyやRecommendationといった機能ができたのが多分2019年の終わり頃で、それからは、「D問題埋め」、「500点埋め」のようなことはほとんどしなくなり、Difficultyを見てやる問題を決めることが多くなりました。
ほぼ緑→水→青と順に埋めていき、4～5ヶ月後の2020年4月には緑～青diffが100％になります。
灰～茶diffは、難しい問題をやる気力がない時にStreakを繋ぐためのストックとして残しています。茶diffはそれほど経たない内になくなってしまいましたが。
未ACの青diffがなくなった2020年4月は、緊急事態宣言によりほぼ自宅待機で過ごすようになっていたため、黄diffを1日2～3問やったりしていました。
しかし、それだけやっても何故か4月はレートだだ下がりで、水色落ちの危機でした。
と思いきや、5月にはV字回復し、また、4月以前は全くと言っていいほど出なかった黄パフォが、5月頃から3回に1回ほどの頻度で出るようになっていきます。
さらに、2020/5/23の第3回PAST（無料だった回）で94点でエキスパートを取得しました。（残り5分でぎりぎり）
黄diff精進の効果が、1ヶ月遅れで出てきたのかもしれません。
ただし、緑パフォの頻度も上がってしまい、6～10月辺りはかなり不安定な時期が続きます。
7月まではなるべく黄diff埋めを進めていて、残りが解説を読んでも辛い問題ばかりになってきて行き詰ってしまってからは、水～青diff程度の問題を求めて、JOIの難易度5～7辺りをやっていました。（できるだけ6～7をやって、5は気力があまりない時用）
あとは時々思い出したように、EDPCやTDPCの残りとか。
何か黒diffからちょうどいい難易度の問題を発掘する術があればいいのですが。
9月には「AtCoder LibraryをJavaに移植」の通り、AtCoder Library（ACL）の移植も行いましたが、これは中身を理解できず、まだまともに使うこともできないものの方が多いです。
一応はACLも整備し、だいぶ武器が増えた気になっていたりもしましたが、10月から11月前半にかけて最高レートから170ほども下がり、再び水色落ちの危機に見舞われます。
その後、11月中旬から2021年2月にかけてレートがうなぎ登りになっていきますが、その要因はおそらくくじかつに毎日参加するようにしたことだと思っています。
以下のHeatmapの右の方くらいが、Unique ACだけ見ると1日1問でStreak繋いでいるだけなのは変わっていないですが、All ACとMax Difficultyを見ると、毎日ほぼ4問以上かつ水～青diffまでやっていることがわかると思います。
競プロを始めてから1年半以上が経過し、これまでに覚えてきたことを色々と忘れ始めていたので、くじかつをやることが復習になり、思い出す効果がかなりあったのではないかと思います。
これを4ヶ月もやり続ければ、1日5問、100日間くらいやっているとして、これまでの全ACの3割程度、茶～青の各diffの半数近い問題をやり直していることになりそうなので、よくよく考えれば結構な分量です。
その割に、解法をほぼ完全に覚えていることもよくあり、30分くらいで楽に終わることもあるので、そこまで辛くはなかったです。毎回必ず6問目までやれているわけでもないですが。
最近の仕事では、プログラムを読むことばかりで書くことがあまりなく、雑にプログラムを書けることは多少の気分転換にもなります。
そして、2020年11月以降は水パフォ以下を出すことがほぼなくなり、出たとしても1600をちょっと下回る程度で済むようになっています。
2021年1月2週目くらいからは青diff以下を落とすことがなく、黄パフォ以上を連発し、黄色になれました。
最後は、青diffの正答率が上がったおかげですね。
黄色になるまでに習得orライブラリ整備したもの
- 三分探索
- BIT、セグメント木の扱い
- ダブリング
- 最小共通祖先（LCA）
- 半分全列挙
- 強連結成分分解
- マージテク（サイズの小さい方から大きい方にマージするやつ）
- 全方位木DP
- 部分集合の全探索（1引いてANDを取るやつ）
- マンハッタン距離の性質
- (K)MP法
- 行列累乗
- 中国剰余定理（CRT）（※ACL）
- 掃き出し法
- 平方分割（※ほぼ概念としてだけ）
- トライ木（※AGCで1回見ただけ）
- 高速ゼータ変換（※過去問で2回くらい見ただけ）
- その他ACLにあるもの（※ライブラリ整備のみで使用実績なしが大半）
こうやって並べてみたものの、下の方はかじっているというだけで、まともに使えると言えるレベルに達していないです。
LCAは第1回PASTのK問題を解けなかったことをきっかけに整備しました。
黄色到達までにやっていないこと
とりあえずぱっと思いつくものを並べてみます。
後で書き足すかもしれません。
名前等だけ見たことがあって完全未習得なもの
- ローリングハッシュ
- 形式的べき級数
- HL分解
- ζ
- アフィン変換（ABC189後追記）
- ポリアの数え上げ定理（ABC198後追記）
- 行列木定理、ラプラシアン行列（第二回日本最強プログラマー学生選手権後追記）
あとはもう名前すら把握していないものがきっと多数あると思います。
解説とか人の記事とか見て、何言っているかわからないこともまだまだよくあるので。
その他やっていないこと１
Codeforcesなどの日本語以外の競プロを一切やっていません。
ARCも増えたし、多分今後も当面やることはないでしょう。
今までに手を出したことのある問題が、AtCoder（PASTやJOIを含む）、yukicoder、paiza、PG BATTLE（問題と解説見ただけ）のものだけです。多分。
その他やっていないこと２
蟻本など、競プロやアルゴリズムに関する参考書を読むことをほぼ全くしていません。
高校数学を復習するようなこともしていません。
これまでの精進方法はほぼ過去問オンリーで、解説だけで理解できなければ、人の提出コードを見たり、追加で多少ネット上を調べたりしたくらいです。
今後のことなど
今まで青も黄色も本気で目指してはいなかったので、橙も本気で目指すことはせず、ゆるくマイペースでやっていきます。
黄色には思いの外早く到達してしまいましたが、当面は黄色維持もままならないことでしょう。
（とか言いつつARC113とAGC052は切り抜けていますが、仮にABC194がRatedだったら落ちているので。）
橙に到達することはおそらく一生ないと思っています。
これまでのレート推移だけ見たら、3～4年後くらいに到達しそうに見えなくもないですが、果たしてどうなるか。
結局今までにやってきているのは、コンテストになるべく全部参加すること、できそうな過去問を解く（解説見て理解する）ことと、出てきたものを適宜ライブラリ整備することだけなので、これまでのAtCoder以外も全部合わせて約2000問の中で出てこなかったことは知りません。
それだけやればある程度のことは網羅されているのかもしれませんが、競プロで必要な知識がほぼ揃っているとは到底思えません。
黄色安定させたければ、いい加減蟻本等にも頼って、まずは穴を減らしていくのが良いかなとは思います。
（出ないものは知らなくてもよいと割り切ってもいいかもしれません。）
とりあえず、穴を減らすという面では、くじかつをまだ当分はやり続けて、青diff以下をほぼ完璧にしていくつもりではあります。
これでレートが上がってはいかないとしても、大きく下がることは避けられると信じています。
それから、面倒くさがらずにやれる範囲で、徐々に黄～橙diffに手を付けていければと思います。
多分仕事が定時帰りが続いているくらいには余力がある時でないと、なかなかやる気にはなれなそうですが。
まずはRecommendationをやるか、くじかつAnotherの5問目までやるようにするか。
あとは、「習得orライブラリ整備したもの」に挙げはしたけど自力ACの実績が少ないものや、未習得だとわかっているものをできるようにしていきたいですが、これもきっとモチベとの相談です。
AtCoderで立て続けに何回も出されれば、さすがに覚えようとすると思います。
知識系や数学系のものは、yukicoderの過去問埋めでもやればかなり拾えるような気がしているので、その内手を出していきたいです。
という感じで、過去問の類だけでもまだまだやれそうなことは残っているので、それで細々と精進を続けていければいいなという感じです。
AHCも始まったので、焼きなましだとかビームサーチだとか、そちら方面のこともある程度はできるようにしていきたいところです。
新しいことを覚えられる過去問に出会ったところで、それがそもそも自分のレベルで習得可能かという問題が深刻になってきているところですが、結局はどこまでその限界と戦うことができるのか次第で、最終到達点が決まってくる気がしています。
「橙に到達することは一生ない」とは、自分が理解できる物事の限界が、橙の水準よりは低いだろうと思っているということです。
もしそれが過小評価だったら、3～4年後に橙になっているかもしれません。
