こんばんは。誇大広告ぎみなタイトルでごめんなさい。
正式タイトルは「AtCoder黄色になるまでに私がしたこと」でお願いします。
この記事では、私が黄色になるまでにしたことや黄色になるのに必要だと思ったこと、勉強方法の提案などを書いていきます。
ちなみに、私は2017/8/1現在、AtCoder黄色真ん中（レート2246）です。
目標は、ICPCアジア地区予選（12月）までにAtCoder橙色になることです。
下図は私のAtCoderのレート遷移と、勉強するきっかけになったイベントを記した図です。
https://atcoder.jp/users/furuya1223
オンサイトコンテストへの参加を目標にすると勉強のモチベーションが上がって良いです。予選通過するとさらに勉強する気になりますし。
途中で壁にぶつかって停滞してから乗り越えるという場所がいくつもありますね。黄に入ってから壁の間隔が狭くなっていますが……
目次
黄色になるまでに使った知識
考察力とDP力が重要
考察力を鍛える勉強法
考察のコツ
最後に（問題集）
黄色になるまでに使った知識
この節はまえがき的な扱いです。
AtCoderのレート変化ありのコンテストで、コンテスト時間中に解いた問題（レート上昇に寄与した問題）で使った知識（アルゴリズム・データ構造）を列挙してみると、以下のような感じになります。
・BFS, DFS
・メモ化再帰
・動的計画法（DP）（確率DP，ビットDPを含む）
・累積和・いもす法
・しゃくとり法
・最短経路（ダイクストラ，ベルマンフォード，ワーシャルフロイド）
・二分探索
・三分探索
・階乗のmod逆元
・ダブリング（数列）
・クラスカル法（最小全域木）
・Union-Find木
・セグメント木（遅延評価なし）
うーん、少ない。こんなもんだっけ？
書き漏れありそう。
貪欲法とか整数の繰り返し二乗法みたいな、当たり前or高度でないものは抜いてあります。
リストには入れていますが、実はセグメント木は使っていなかったりします（AtCoderのRatedなコンテストでは）。
ビットDPも使ったこと無いような気が……
上記のリストは「黄色になるまでに基本的には使えるようになっていた技術」ですかね。
使わなかった知識には以下のようなものがあります。
・最大フロー、最小費用流
・橋，関節点検出
・強連結成分分解，トポロジカルソート
・2-SAT
・遅延評価セグメント木，starry-sky木
・木のダブリング
・行列累乗
・幾何の色々（点と直線の距離とか凸包とか）
・ローリングハッシュ、接尾辞配列、trie木などの文字列処理
・平方分割
・木の重心分解・HL分解
・スライド最小値
・kD木
・最小全域有向木
・平衡二分探索木
上記の技術が身についていなくても黄色にはなれるってことですね。私が証明です。
もちろん、身についていた方が黄色にはなりやすいですし、黄色になってからもレートを上げやすいと思います。
ですが、知識よりも支配的な要因があると私は考えています。考察力というやつですね。
考察力（とDP力）が重要
AtCoderでは特にそうなのかもしれませんが、考察力が重要だと思います。当たり前ですね。
あと、DPを使う技術は重要ですね。DPは汎用性が高いので、優先して学習する価値があると思います。
よくあるDP（貰うDP）、確率DP、ビットDP（TSPなど）、区間DP、桁DP、などなど、いろいろなDPを経験しておくと良いと思います。
DPについては、練習問題の解き方を勉強して、どういうタイプの問題をどう変形してDPに持ち込むのか、を考えると良いです。
時間計算量もしっかり意識しましょう。（コンテスト本番にMLEは今のところ未経験です）
では、考察力を鍛えるにはどうすればいいのでしょうか。
考察力を鍛える勉強法
コンテストで解けない問題があって、終わってから解説を見たら、想定解法が自分の知らない知識を使っていた。
なんてことがあっても、あまり悔しがる必要はありません。その知識を勉強すればいいんです。
「解説に知らない知識は無いのに、解けなかった」となると、悔しいですね。「解けたのにー！」みたいな。解けなかったのに。
そんなケースを減らすにはどうすればいいでしょうか。
答えは、「解けない問題の解説を見て理解する」という経験を積むことです。（個人の見解です）
「たくさん問題を解く」というのは、AtCoder青を目指す段階では有力だと思いますが、青になった人は、考えて解法が分かるような問題に取り組む必要は無いと思います。
実装力・早解き力の訓練にはなるかもしれませんが、黄色を目指す上では、重要度は圧倒的に「考察力＞実装力・早解き力」だと思います。自分が考察特化型だからそう思うだけかもしれませんが。
問題を見て、すぐに解説を見るのは良くないです。
問題を見て、20～30分程度考えて、解法が分かればそれは「分かる問題」なので捨てましょう。
20～30分程度考えて分からなければ、解説を見ます。分かりそうなら考える時間を延長してもいいです（最長で1時間ぐらい）。
そして、解説を理解できれば、実装する必要は無いと思います。するのも無駄ではないと思いますが。
解説を理解できたけど実装できるか不安、あるいは、解説をなんとなく理解できたけど理解が正しいか不安、という場合は、実装して確かめると良いと思います。
どう考えても解説が理解できない場合は、図を書いたり例を挙げたりして頑張って理解を試みるか、不明点を可能な限り明確にした上でツイッター等で助けを求めましょう。それでもダメなら一旦諦める。
上記のようなトレーニングを繰り返すと、考察力が上がると思います。
「そういえば階差数列で考える問題があったな」とか「操作を逆順にするとシンプルになる問題があったな」とかの経験が貯まっていくので、考察の選択肢が増えると思います。
「解いた問題数」よりも「見た解説数」でレート変化が決まると言っても過言ではないと思います。
考察のコツ
コンテスト中に考察を行うときのコツみたいなものを、私が思いつく限り書いていきます。
（※効果には個人差があります）
計算用紙をめっちゃ使う
大事です。コンテスト三種の神器「大量の白紙・シャーペン・消しゴム」。海外のオンラインコンテストだと「Google翻訳」が加わって四種になります。
小学生が使うような、1cmの方眼ノートもあると便利です。ダイソーでも売ってます。
頭で考えて全く分からない問題でも、書いて書いて書きまくれば本質が見えてくる、というようなことはよくあります。不思議ですね。
意味の無さそうなことでも、とにかく書きます。何でも書きます。
制約をきちんと確認する
制約からO(N^2)が間に合うのか、などを考えます。
O(N^2)が間に合うのならO(N^2)で解けばいいのです。無駄な高速化は悪手です。
黄色になるまでは、O(logN)は定数だと思って大丈夫でした（個人の経験）。
1+1/2+1/3+……+1/N=O(logN) という知識が無くて「O(NlogN)が間に合うな…… logNということは二分探索か？」とか考えていて落とした問題があるので気を付けましょう。
平方分割でO(N^2)をO(N√N)に落とすような問題もあるようですが、自分はまだ経験していません。
サンプルケースのシミュレーションを分析する
サンプルケースを紙の上でシミュレーションするのは当たり前ですね。（問題によりますが）
このシミュレーションを徹底的に分析しましょう。
数列が出てきたら階差を取ったり累積和を取ったり。
最小全域木のように複数の最適状態がある場合は、それを全部チェックしたり。
わざと最適でない状態を挙げてみて、最適状態との違いを考えたり。
操作を逆順にして考えるテクニックはちょくちょく出ますね（上書き操作を入れ替えると確定操作になるというのはAtCoderで2回ほど出ましたね）。
サンプルケース以外に例を用意する
問題によっては難しい場合もありますが、できるならやりましょう。
特に「ある操作が可能かどうか判定せよ」みたいな問題の場合は、「シンプルなのに不可能な例」を挙げると、本質が見えてくる場合があります。
オリジナルのケースでは、くれぐれも入出力を間違えないようにしましょう。
思いついた解法の時間計算量をちゃんと確認する
O(N^2)のつもりで実装してたら実はO(N^3)であることに実装途中で気づく、みたいなことがよくあります。私だけでしょうか？
自分への戒めです。
複数の操作を同一視して扱えるようにする
問題によって、操作Aと操作Bが用意されているものがあります。
これを、解釈の変更や問題の変形によって、同一の操作とみなせるようにするとうまくいく、という問題があります。
ARC029C「高橋君と国家」http://arc029.contest.atcoder.jp/tasks/arc029_3
ABC010D「浮気予防」http://abc010.contest.atcoder.jp/tasks/abc010_4（前述の「使わなかった知識」に含まれるアルゴリズムまたはデータ構造を使う問題です）
以下の問題は同一視ではありませんが、共通点を見出すとうまくいく問題です。
ARC071E「TrBBnsformBBtion」http://arc071.contest.atcoder.jp/tasks/arc071_c
最後に（問題集）
せっかくなので、「DP・累積和以外の特別な知識を必要としない問題」をいくつか挙げてみます。
DPを使う問題も、確率DP、ビットDP、区間DPなどは登場しません。普通に前から埋めていく、単純な漸化式を使うDPしか登場しないはずです。
累積和は登場したかどうかちゃんと把握していませんが、出たとしても区間和を高速に求める程度の用途です。
幅優先探索・深さ優先探索は出てくる問題もあります。基本ですからね。
カッコ内の数字はAtCoderにおける配点です。（昇順に並べてあります）
400,500あたりは、配点に対してやや難しめの問題な気がします。
ですが、特別な知識は不要なので、紙とペンを用意して考えてみましょう。
（300）ARC060 C「高橋君とカード / Tak and Cards」
（300）ARC072 C「Sequence」
（400）こどふぇす2016予選C C「二人のアルピニスト」
（400）AGC011 B「Colorful Creatures」
（400）AGC004 B「Colorful Slimes」
（400）AGC017 B「Moderate Differences」
（400）ARC078 D「Fennec VS. Snuke」
（500）AGC014 B「Unplanned Queries」
（500）ARC071 D「井井井 / ###」
（500）ARC060 D「桁和」
（500）AGC010 B「Boxes」
（500）AGC011 B「Mysterious Light」
（600）ARC070 D「No Need」
（600）ARC071 E「TrBBnsformBBtion」
（700）こどふぇす2016予選B D「Greedy customers」
（700）AGC016 B「Colorful Hats」
（700）AGC013 C「Ants on a Circle」
（700）ARC076 E「Connected?」
（700）AGC014 C「Closed Rooms」
（700）AGC016 C「+/- Rectangle」
（700）AGC012 B「Splatter Painting」
（800）AGC011 C「Squared Graph」
（800）こどふぇす2016予選C D「Friction」
（900）ARC072 E「Alice in linear land」
（1000）AGC017 C「Snuke and Spells」
頑張って考察力を挙げて良い黄色コーダーライフを送りましょう。
私もオレンジ目指して頑張ります。