AtCoder緑色になったので今までを雑に振り返る
はじめに
2019/6/1に行われたM-Solutions プロコンオープンにて緑コーダーとなることができました!!
🐫→🐢
— severrabaen (@severrabaen) June 1, 2019
本日をもって、緑コーダーとなることができました!!
やった!!!!
茶色に落ちないように(レートを上げられるように)これからも精進します! pic.twitter.com/pO1hIUr3fb
chokudaiさん曰く、初心者ではなくなったらしいですが、これから一層頑張っていきたいと思います。
何度も言ってるけど、AtCoder的には「緑くらいで一定の評価が得られて、水色くらいで結構な割合の業務においてはカンストレベル」って言ってるので、この辺が初心者なわけがないのよね。茶色については悩ましいところかなぁと思う。
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) May 10, 2019
なので、競プロを始めてから今までを大まかに振り返ってみたいと思います。
こういう記事を書くのが初めてなので勝手が分からないです(茶色になったときはあまり書く気が起きなかったです(は?))。なので読みにくいと思いますが、その時はごめんなさい。
使えるようになったアルゴリズム
思いついた順に書きます。抜けを思い出したら逐次追加します。
・bit全探索
・二分探索
・累積和(imos法含む)
・gcd、lcm
・(簡単な)DP(具体的にはEDPCのFあたりまで)
・最短経路探索(Dijkstra、Warshall-Floyd、Bellman-Ford)
・二項係数nCr
・階乗
・桁和
・Union Find
・尺取り法
・DFS、BFS
・幾何の色々(線分交差判定等)
最初期(氷河期)
上のツイートのレートのグラフを見ると分かりますが、最初期は特にレートの上がり幅が小さいです。超言い訳がましいですが、プログラミングにそんなに慣れていないままコンテストに参加したりコンテストにスマホコーディングで出ていたりした(事情があったので)のが大きいなどと考えています(本当に言い訳に過ぎませんが)。
ただ実際、「初期のレートが低いが故に現在のレートも低くなってしまっている」という人はいると思うのでそういう人がこの記事を読んで参考にしてくださると嬉しいです。
着色前後
灰色コーダーだった頃、AtCoder ProblemsでABCのC問題を見て、今の自分にはレベルが高すぎると感じたのでABCのAB早解きを頑張りました。個人的には恒常的にAB合わせて5分を切れると良いと感じています。これだけ続けていても十分にレートは上がるはずです。実際こんな調子で僕は茶色になりました。
あとは、ひたすらに問題を解きまくっていました。またもや持論なんですが、過去問を解くと、各点数のレベル感が掴めるし、競プロにおけるアドホック的思考が学べるのでとても良いです。灰色時代から色が着色するあたりまで毎日ACを続け、最終的には204日間続きました。以下に本記事を公開するまでの精進の記録を載せます。
茶色から緑色へ
正直灰色から茶色より楽だったかもしれません。恐らく最も大きい要因はABCのC問題が本番中に通せるようになったことです。
僕個人の意見を言うと、最近のABCのC問題は基本的なアルゴリズムの知識を問う問題が多い気がします。実際、直近3回のABCのC問題で使われるアルゴリズムを見ると、順に、bit全探索、imos法、数学なので、基本的なアルゴリズムの理解、問題への応用をできるようになることがとても重要だと思います。
これを続けることによりABCではC問題までをペナ込みで20分以内に通せるようになり、順調にレートは上がっていきました。
結局AGCに1回も参加することなく緑色になったので今回はAGCについては触れないでおきます。
まとめ
・最初の内はABCのAB早解きを目指す。できるようならC問題も通す。
・精進する。
・蟻本等を読んで様々なアルゴリズム、データ構造を理解する&使えるようになる。
水色にもなれるように頑張ります!!