AtCoderで緑になりました
茶Coderになってから二ヶ月経ち、ようやく緑Coderになりました!
一度レートが下がりまくったときはどうなることかと思いましたが、その後は特に何事もなくレート上がりました。よかった……。(下がったのはドワンゴコンで水パフォが出てしまって無駄にレートが伸びてしまった説が濃い)
緑色というと、「エンジニアとしてもある程度の安心感」とのこと(chokudaiさん談)なので、自尊心高まりますね。Unityとかソフトウェア開発もやらないとなあ
さて色変したからには「緑色になるまでにやったこと」みたいなのをまとめてみようかなと。水色になるまで、とかよりは有用性低い感じはしますが、競プロはじめてすぐの人へのTipsになるといいなと思います。
まず、どのコンテストに出たらいいの?という話。
AtCoder上でのコンテストは、ABC級、ARC級、AGC級(+unratedのやつ)に分類分けされています。コンテストの名前の左に付いている丸の色です。青ならABC級、橙はARC級、赤はAGC級ですね。
AtCoderのレーティングシステムには、コンテストの参加回数が少ないうちはパフォーマンスよりレーティングが大分低くつくような仕組みがあります。これがあるので、レートを上げようとするならコンテストにたくさん出ておこう、となるのですが、ここでARC級とかAGC級にも出るべきなのか?という疑問が浮かぶと思います。
この質問への個人的な解答は、「No」です。出たほうがいいよ、という人もいるんですけどね。
私がこう思う理由ですが、ARC級とかAGC級とかに出てもあまり問題が解けないからです。結局1完とかになってしまうんですよね。そうすると、あまりパフォーマンスが出なかったりして、レートもあまり伸びない。ひどいと下がったりしちゃいます。
そうなると問題になるのが、自分の競プロのモチベ維持です。やっぱり、競プロが楽しくてもレートが伸び悩んだりするとあまりいい気分にならないと思いますし、急にARCとかに参加して問題が解けなかったから「自分は競プロに向いてないのかな……」みたいに悩んじゃうとか、そういう人も居るんじゃないかなと思ったりします。
別にARC級とかAGC級の問題が最初解けないのなんて当然で、私も700点問題とか自力で解けないし、ちょっとずつ解けるようになっていくものだと思います。
やっぱり競プロ始めてすぐは成功経験の方が継続の糧になるので、無理に上級のコンテストに出なくてもいいんじゃないかな、と思うわけです。
(なんか書いてたら長くなってしまったな…)
あとは、緑までに知っておくべきアルゴリズムの話です。
パッと使えるようにしておくべきものは、こんな感じ。
(・C++のSTL、queueとstack、map、setとか)
・素因数分解、GCD、LCM
・mod p逆元、二項係数(nCr)、二分累乗法、二分乗法(正しい名前なのか不明)
・二分探索
・貪欲法
・一次元DP、典型的な桁DP
・DFS、BFS
・しゃくとり法
・累積和、(imos法)
逆に今まで使う緑diff問題に出会ったことがないアルゴリズム
・UnionFind木、セグ木、BIT
・最小全域木(クラスカル法)
・ベルマンフォード法、ダイクストラ法
ベルマンフォードとダイクストラは、緑で出てもおかしくない気はしますが、まあとりあえずこんな感じで。
最後にですが、やっぱり精進は毎日続けといたほうがいいです。緑くらいまでだと、まだたまにこのアルゴリズム知らなかったから解けなかった!みたいな事態が発生するので、過去問で演習量積んでおくのはアドバンテージになると思います。解説までしっかり読んだり動画見たりしましょう。
というわけで、以上です。高校卒業までに青になることを目標に頑張っていきます。