実績解除：AtCoder水色になった
よかったね。
実は2019年内での入水を目標としていたので、少し複雑な心持ちです。
現在のレートが1227で、ちょっと低めの緑パフォを出すと終了なので油断できない状況です。AGCの参加はしばらく控えるかもしれません。
というわけで、水色になるまでにやったこと 書いていきます。
自己紹介
電子情報系を専攻する大学生です。中学生の頃にhspという言語に触れていましたが、本格的にプログラミングを始めたのは大学生になってからです。
灰色になるまでにやったこと
rated初参加すると灰色になれました。ただ、初参加のコンテストはABC126でunratedだったので他の人より灰色になるのは苦労した方かもしれません。（？？？？？？
茶色になるまでにやったこと
ABC３完を安定させました。時々Dも解けたりすると緑パフォが出ます。ABCの前３問は大学でやる基礎プログラミング講座レベルの問題が多いので、大学での勉強が結構活きたかもしれません。
緑色になるまでにやったこと
ABC４完を安定させようとしました。３完まで早解き、Dはがんばる。って感じで。緑下位くらいのパフォが安定していましたが、それだと中々色変できないので４問早解き練習しないといけないのかなあと思い始めました。それとは関係なく、なんかよくわからないけど最強コン予選で水パフォが出て色変しました。
水色になるまでにやったこと
水パフォが出ないと流石に入水できないことに気付いて、夏休みあたりから過去問を解き始めたり蟻本を買って読んだりしました。蟻本難しいし、たぶん入水で使わない知識が多いので結局精進が一番だなと思います。４完早解きは当たり前で、５完を目指すのが丁度いいと思います。多倍長整数でゴリ押していたらなんかよくわからないけど青パフォが出て色変しました。
精進について
こんな感じです。最近は結構ストリーク気にしてます。
虚無埋めはあまり好きじゃなくて、（とはいえ早解き練習のために必要な場合はあります。）水〜青difficultyの問題を好んで解いていました。水difficultyの問題でも数日悩んでも解けないような問題は多々ありました。というか最初はほとんど解説よみよみと写経の日々だったような…。
解かなければならないけど解けるかわからない程度の難易度に挑戦するのは大事だと思います。問題の傾向や計算量の感覚、TLEが来た時の定数倍高速化や少数のWAが来た時のコーナーケースのチェックなど習得できることがとても多いです。
何より、「制約の裏にどんなアルゴリズムが透けて見えるか？」「本質は何か？」などを問題設定から直観する能力は精進以外で手に入らないと思います。いわゆるエスパーと呼ばれている攻略能力です。
例えばこれ。
問題を読めばすぐに何をすればいいか直観できるはずです。
AtCoder始めたての頃の自分だったら手も足も出ない問題だったろうと思います。エレガントな解法があるので（とはいえ使い古されていますが。）結構好きなタイプの問題です。
大学受験とかで出たら正答率めちゃくちゃ低そうだよね。
あと最近のはこれ。
このときABF３完とかやってました。
辞書順といえば貪欲法で、なんか障害物のある数直線上をぴょんぴょん動くのはDPで…。といった感じで考えていると何かをエスパーできました。この時は厳密に証明していませんでしたが、反例が思いつかなかったのでええやろと思っていました（ゴミ）
こんな感じで、エスパー力が大事。それを鍛える精進がめっちゃ大事！
覚えたアルゴリズムについて
そんなに多くはないです。エスパーと考察が大事です。
・繰り返し二乗法（pythonにはpowがあるから気にしなくてヨシ！）
・累積和（これができないと緑行くのも難しくないか）
・二次元累積和（未だにソラで書けません）
・dijkstra法（実はグラフに落とし込んでdijkstraで〜すっていう問題がこわいよね）
・bellman-ford法（負閉路検出が難しいですね）
・warshall-floyd法（毎回ソラで書いています。制約でわかる。）
・prim法（pypyだとクラスカル法は定数倍が重くて使えません。）
・Binary-Indexed-Tree（使わんでもどうにかなる場合が多い）
・Segment-Tree（使わんでもどうにかなる場合が多い）
・UnionFind（頻出アルゴリズム。結構好き）
・トポロジカルソート（ちょっと好き）
・mod逆元（フェルマー小定理でやるやつしかわからない）
・素因数分解（平方根オーダーでできるやつ。sieveはわからないので人のを貼る）
・ナップザックDP（２次元になると遷移で頭バグる）
・桁DP（よくわかっていない）
・文字列DP（制約を見ると解法がわかるよね）
・DFS、BFS（pypyは再帰が遅いのでstackでdfs書くことがあります）
・順序付きキュー（pythonにはheapqがある）
・しゃくとり法（実はソラで書けません）
・LIS（結構好き。二次元で片側ソートするやつも好き。入れ子と仲がいい。）
・ローリングハッシュ（名前かっこいいけどまともに使ったことないわ）
どんな記事にも終わりはある
ここ１年で離散数学めちゃくちゃ上手になった気がします。緑落ちしないでなんとかこのまま青まで行きたいな〜〜
その前に、留年しないといいね。
