はじめに
はじめまして。今回、AtCoderのABC276にて入緑した、makaserori (https://twitter.com/358_Serori_Dros) といいます。調子に乗ってパソコン甲子園の宿泊先からこの記事を書いています。
機械科の高専生で、ギターとか音楽鑑賞、野球観戦にライブ参戦やら、ApexとかのFPSを趣味でやったりしてます。
この記事では、僕が緑になるまでにやったことを記していきます。よかったら読んでいただけると幸いです。ついでに、灰色や茶色時期についてもまとめて書いてしまいます。
行き詰まってたり、「競プロ始めてみたいな、どんなものなのかな」って思ってる人には「こんな感じでもいいんだ」という緩さを知って貰えればと思います。(正直、使える内容か、と問われたらだいぶ怪しいですw)
個人の競プロ歴と能力について
競プロを始めたのは2021/2頃です。ちょうど冬休みに入るタイミング、友人に「やってみない？」と誘われたのもあり、AtCoderにて競プロを開始することに相成りました。
戦歴はこんな感じです。(わざわざ書くほどでもない？？)
- 2021/2 競プロ開始
- パソコン甲子園2021 本選
- 2021 JOI Bランク
- 2022/3 入茶
- パソコン甲子園2022 本選
JOIの二次を突破できなかったことに関しては明らかに自分の実力ですが、PCKについては誘ってくれた相方の力あってこそです。(それについては後述します)
緑までに履修したもの(実装できるもの)
まずは、入緑するに至った自分の技能について述べたいと思います。
AtCoder Problemsによると、
こんな感じだそうです。あんまり量はこなしてないみたい。
履修したアルゴは、
- 全探索 : n重for(再帰) ,順列全探索
- 累積和 ： 典型 ,いもす法
- dp : 典型的dp ,bit dp(ちょっと怪しい)
- 幅優先探索(BFS)
- 深さ優先探索(DFS)
- 二分探索
- Union-Find木
- ダイクストラ法
- ワーシャルフロイド法
記入漏れがありそうですが、自分で浮かぶものはこれくらいです。
加えて、応用的なものなどはあまり出来ていないので、入門レベルで止まっているアルゴもあります。
つまり、裏を返せば、この程度のアルゴリズム知識でも緑にはなれるということです！！！
自分は、この中でも「グラフ理論系統」と「dp」が大事だと思います。"DはDPのD" なんて言葉もあるくらいです。
とにかく緑になるためには「早く4完」することが大切です。そのため、D問題で多い、グラフを使うものやdpを用いるものは、学んでおいて得しかないです。
(これは完全なる個人的所感なんですが、C ,D問題に出てくるレベルだと、再帰やBFS,DFSよりDPの問題のほうがDiffが高い傾向があると感じています。)
ついでに、初心者時期/入茶時期 についても書こうと思います。
初心者の頃やったこと
数は多くないです。ほんとに基本中の基本しかしてない。
-
APG4b(C++入門 AtCoder Programming Guide for beginners) : https://atcoder.jp/contests/apg4b
基本中の基本です。これで習った、やったことはどのアルゴリズム学んでても当たり前のように使うので、まじで大切です。今のところこれで出てきたデータ構造以外にであったものの数はそう多くないです。 -
ABCの過去問(A,B問題) : https://kenkoooo.com/atcoder#/table/makaserori
サボり癖あるので今でも全然埋まってないですが、過去問やることで基本的な感覚がつかめます。ほんとに大事です。
どのレート帯でも共通して言えると思うのですが、「過去問を解く」ってのが、習ったアルゴの練習・知らないアルゴを学ぶ、といった両面で大事だと思います。いわゆるアウトプットの場です。
初心者を抜け出す、という面では、A・B問題をたくさんこなしていけばいいと思います。
灰→茶 の時期にやったこと
- とにかく何かアルゴリズムを学ぶ
僕の契機はJOIでした。灰色でも一次予選は通過できたのですが、二次でBFS等を用いる問題の前に敗北し、Bランクで終了。
また、このタイミングは、パソコン甲子園本選に出場できたものの、3完というお粗末な結果に終わり(相方のキャリーでチーム7･8完くらいまでいきました)、レベルの高さ、というものを知った直後でした。
これが本当に悔しくて、そこからなぜかBFSを…とはいかず、なぜかDFSから勉強を始めました。
その結果がこれです。
始めて以降ずっと横ばい傾向だった折れ線が、アルゴの勉強をし始めた1月あたりから著しい上昇傾向に転じました！
なので、灰色→茶色 において大切なのは、「武器となるアルゴリズムを持つ」ことです。もう既に1つ学び終えてるよ、という人は、それを掘りさげてみる、あるいはほかのアルゴリズムをやってみることをオススメします。武器があれば絶対茶色になれます。
- ABC-C問題をたくさん解き、C問題の感覚を掴む
前述したようにアルゴリズムも大事ですが、それを踏まえて、茶色になるために何よりも大事なことは、「C問題を解けるようになる」ことです。
C問題では、アルゴリズム以外では、A・B問題で求められなかった "考察力" が大事になってきます。
例えば、「$ O(N^2) $ になってしまう解法をどう改善するか？」だったり、「愚直シュミレーションをする代わりに情報をどう持つか？」などなど。
僕個人は、計算量 $O(N^2)$ の改善が苦手でした。累積和つかったり、与えられる数列の性質より条件分けできたり…など、過去問を解くことでイメージが湧きやすくなってきます。
個人的な思い
やはり大切なのは「断絶しないこと」と、「質問できる人を持つこと」だと思います。
自分の場合は、灰色の時期には「PCKに出る」、茶色の時期は「緑になる」という思いが、競プロを継続させてくれました。
正直、自分もこの半年で何回か辞めたくなりました。解いても解いてもレートが上がらない時期と、私生活や学業で躓いた時期が重なり、実際辞めかけた時期もありました。
(折れ線が2022/6→2022/8 で長い直線になっているのはこれが理由です. 直近も780付近から上がれなくて苦しかったです)
でも、一度「ACの喜び」を覚えていたから、もう一度帰って来れたんだと思っています。
永続することより、断絶しないことを大切にして、ちょっとずつ頑張ればいいのではないかな、と思います。
また、いつでも聞けるような知人を持っておくのは本当に大切だと思います。自分の場合は、誘ってくれた友人が青色(現黄色)だったので、気軽に聞くことができました。
身近に居なければ、Twitter上の界隈の人に聞いてみるなど、「自分より能力がある人から吸収する機会」を設けられれば、より成長できると考えます。
また、自分は解説読んだ後にACする後味の悪さがなんとも苦手で、一週間同じ問題の解法を考え続ける、なんてこともよくあります。
これは改善していくべき点だと思っていますが、逆に「ギリギリまで考える」ということは、自分の能力向上に繋がっていると感じています。粘り強さを獲得できると、通せたときの喜びが何倍にも膨れ上がるのでちょっとだけオススメです。
さいごに
結局何を書きたかったのかよく分からないのですが、まとめると「1年9ヶ月かかって緑になれる人もいるから、諦める必要はない」ってことです。
成長は人それぞれ、といいますが、人それぞれのなかでも大分下を行っている自信があります。
そもそも灰色→茶色に一年間も要した人ってそんなに居ないと思います。でもなんとか続けられました。
上を見たら空しかないですよね？だから下を見ましょう。上なんて文字通り青天井です。
もしあなたが一年で入緑できたら、私より優秀です。そうやってモチベを上げていくのも大事だと思います。
PCK2022本選で渋々な結果を出した後のABCで入緑するのは不思議な気分でした。
(あと入緑ツイートアホほどお祝い貰えて嬉しかった。こういうのきっかけにいろんな人と仲良くなりたい。)
今後は、PCK終わったのですこし休んで、学校のテストを終えたらまた再開しようと思います。とりあえず、入水するまでは続けていこうというのが目標です！
書籍とかを使った勉強と、ARCに参加することが今のところの予定です。激冷えが怖いです。
以上、まかせろりでした。
長文失礼いたしました.
敬具