【AtCoder入青】数弱コーダーの戦い方
はじめに
AtCoder Beginner Contest 378にて遂に念願の青コーダーになる事ができました。
レートが停滞したり下がったりした時、こんなに努力しているのにレートが上がらないなんて、自分の能力ではいくら努力しても青コーダーになれないんじゃないかと何度も挫けそうになりました。それでも諦めずに精進を続けていたところ、遂に青色になる事ができました。
この記事では自分の事について書きますが、多くの悩める競プロerたちの役に立てば幸いです。
私のスペック
職業
会社員（ITエンジニアではない）競プロ歴
ABC初参加から約1年4か月が経ちましたプログラミング歴
競プロを始める前はpythonを少し触っていましたが、アルゴリズムは全く知りませんでした（BFSナニソレオイシイノ状態です）。競プロはc++でやってます数学力
よわよわ。Σ見ると吐き気がします。計算ミスが多いです。昔はそこそこ得意だったはずなのですが、今はこんなです。しかも得意だったのは数Ⅲで、競プロに関連が深い数ⅠAは苦手だった記憶があります
私の勉強法
問題を解く
解けても解けなくても解説を見る。解けなかった場合は解説ACする（ただし理解不能な場合は諦める）
問題を分類し、後日また解く価値があると思った問題は記録しておく（忘れた頃にまた解く）
1～3を繰り返すだけです。特に3が重要で、どういうアルゴリズム・考察テクニックを使えばその問題を解く事ができるのか、自分なりに咀嚼し分類しています。
地頭の良い人は「ナップサックも巡回セールスマンもダイクストラも全部DP」で済ませてしまうかもしれませんが、凡人の私にはそうはいきません。私にとっては、部分和DPもナップサックDPも桁DPもbit DPも対戦ゲームDPも全く異なるテクニックに見えてしまいます。同じDPと言われても納得できるだけの頭がないので、異なる典型として覚えています。ちなみに、私はDPだけで26個もの典型に分けています。
これには個人差が大きいと思いますが、凡人の私には凡人なりの戦い方があると思っています。
入青するまでに勉強した典型テクニック一覧
典型アルゴリズム・テクニックとして約150個勉強しました。このページで全て紹介するには多すぎるので、別サイトにまとめました。該当する問題も載せていて、全部で約500問あります。
リンク先の一覧は、青コーダーになる為に必要な典型アルゴリズム・テクニックの目安にもなるかと思います。
レートが伸び悩んでいる方などに活用して頂けると嬉しいです。
入青するまでに解いた問題
ABC過去問
問答無用でこれが一番勉強になりました。問題数が多い事、diffがある事により自分に適切な問題かどうか分かる事、snuke氏による動画解説が分かりやすい事など、最強の勉強コンテンツです。
特にsnuke氏の動画解説は神で、解法だけでなく、どうしたらその解法を思いつけるのかというところまで解説してくれています。また、その場でコーディングしてくれるので、強い人の書き方を知る事ができ、とても勉強になりました。
PAST過去問
これも勉強になりました。ABCと同じような傾向の問題が多いですが、ABCよりも考察や実装の手間が加わっている問題があり、勉強になりました。
典型90（★6まで）
評判通り良質で、とても勉強になりました。ただし問題数は少ないので、この他にも精進量を稼ぐ必要がありました。
中級100問
私は序盤でこの問題集を解かせて頂きました。典型別に勉強でき、基礎を固められたと思います。
EDPC（A-V、X）
DP入門として良く紹介されるコンテストで、私もありがたく解かせて頂きました。ただ、DPの練習としては圧倒的に量が足りないと思います。DPの実力は、ABC過去問など主に他の問題で養われたと思います。
やりかけてやめたもの
ARC過去問埋め
10問ぐらい解きましたが、考察メインの問題が多く、自分が伸ばしたい典型力を鍛えるのに役立つか懐疑的になりやめました。難しすぎて単に挫折しただけかもしれません・・・。
蟻本
勉強になる点は多いと思ったのですが、行間を読めない私には読み進めるのがつらく、やめました。snuke氏の動画解説ぐらい丁寧でないと理解できない・・・。そもそもABCの公式解説も理解できないものが結構あります。
これからやりたい事
JOI過去問埋め
実は入青する直前から、JOIの難易度7を埋め始めていました。JOIの問題は、ABCの問題よりも考察あるいは実装難易度が高めだと感じました。じっくり取り組んで典型力・考察力・実装力をつける問題としてかなり有用だと感じました。
体感的には、現在水色で青色を目指す人にとっては、難易度5～7ぐらいの問題を解くのが丁度良い精進になる気がします。
入水時との違い
覚えている限りの差異を書きます。
覚えた知識（アルゴリズム・テクニック）
入水後に覚えた知識を列挙します。特に前半太字の知識が基礎力の強化につながった感じています。テクニック名は私独自のものもありますので、詳しくは前述の「絶対にAtCoderで青コーダーになる！典型別 良問500選」をご覧ください。
細字も出題頻度が低いだけで無駄な知識とは思っていません。ただし、ここで挙げた知識よりも、後述する「覚えたテクを使い倒す力」がレート向上に寄与したと思います。
拡張ダイクストラ法
ダブリング
遅延伝播セグメント木
二分探索による平均最大化
半分全列挙
ヒストグラム最大長方形（スタック利用）
Nimとgrundy数
累積和やセグ木利用によるDP高速化
ローリングハッシュ
マンハッタン距離・チェビシェフ距離
データ構造をマージする一般的なテク
平方分割
前処理DP
約数系包除
ハッシュで一致判定
二分探索による中央値探索
インラインDP
円環DP
全方位木DP
戻すDP
DP in DP
挿入DP
Top 2を持つDP
重み付きUnion Find
双方向リスト
Mo's Algorithm
LCA（最小共通祖先）
木の次数列
橋・関節点
中国剰余定理
Lucasの定理
行列累乗
掃き出し法
偏角ソート
最大フロー・最小カット
牛ゲー
Trie木
Suffix Array
覚えたテクを使い倒す力
各アルゴリズム・テクニックに対する理解度が上昇したと感じます。例えば、入水時にはDFSをすれば良いと分かってもそこからが大変で、頭を混乱させながら必死に書いていました。今はDFSの動きを頭の中で想像しながらコードを書けるようになった感じです。
また、各テクに対する理解度が上がった事で、問題を見た時に使えそうなテクが頭に浮かびやすくなり、結果的に考察力も上がった気がします。
色々なタイプの問題を解き、精進量を増やせば増やすほどこの力がつくと思います。やはり精進は大切ですね。
実装力
地味に上がっている気がします。プログラムを実行したときの動作イメージを持ちながらコーディングができるようになってきたと思います。
また、関数を多用するようになりました。関数化する事で、思考を整理しやすくなり、同じコードを何度も書く必要がなくなり、変数名被りのリスクも減らせるので、基本的にメリットしかないと思っています。c++のラムダ式なら書く場所が離れる事もないですし、[&]宣言で引数も適当に扱えるし、競プロにはうってつけです。
とは言え、未だに結構バグを出してしまいますので、まだまだ伸びしろがありますね。
最後に
長文になってしまいましたが、ここまで読んで頂いてありがとうございました！レートが下がって精神的にやられる事もありますが、やっぱり競プロは楽しいです。好きこそものの上手あれ。