【色変記事】競プロを始めて1年7ヶ月で入緑できました

はじめに

63回目のコンテスト参加となる、ABC277で入緑を果たすことができました。節目を迎えたので、私が今まででどんなことをやったのか、何を学んできたかなどをまとめてみました。ついでに入茶したときのことも書いています。

バックグラウンド

幼いころからゲームを通してプログラミング(特にゲーム制作)に興味を持っていたのですが、いかんせん勉強の仕方が全くわからず、中学の技術の授業でScratchに触れた程度の経験しかありませんでした。中学時代はコンピュータ部に所属していましたが、部活とは名ばかりのゆるいものだったのでそこでも何もしていませんでした。一応タッチタイピングの練習は欠かさずしていたので、世間一般的には「タイピングが速い」くらいになれました。¹ここが今の速解きに貢献している気はします。

さて、高校でもコンピュータ部に入りましたが、幸いにもこちらのコンピュータ部はちゃんとした部活だったのでプログラミングに触れることができました。なんでも「ゲーム制作とかもサポートするけど、その前に基礎固めとして競プロちょっとやれ」というスタンスだったので、APG4bをやることになりました。APG4bは非常に優秀な教材なので、前述の通りプログラミングへの意欲だけはあった自分はそれなりのスピードで読み込んで成長でき、学年内で2番手くらいの立ち位置になれました。とはいえコロナの影響で休部になったので5月は丸々やっていなかったし、for文の理解に1週間かけたり、多重ループ,多次元配列の理解をしたのが競プロに触れてから約2ヶ月後だったりと、土台完成までにかなり時間をかけてしまいましたが…²
1年目の夏休みくらいからようやく本格的に競プロ(ABCの問題等)に取り組んだ感じです。家で競プロに取り組むようになったのもその頃からでした。

私は別に地頭がいいほうではないですし、なんなら数学は昔からとても苦手な教科でした。AtCoderに触れてから数学アレルギーをほんの少しだけ解消できている気はしますが、依然苦手です。なので数学パズル寄りといわれるARCには参加せず、典型アルゴリズムなどで戦えるABCに熱を入れていました。幸いにもプログラミングへの意欲はあったので、アルゴリズムやデータ構造を学ぶのはあまり苦ではなかったです。

入緑時点での統計情報

多分、入緑した人の中では結構精進してたほうだと思います。E問題とか水Diffも少し解けていますが、その半数程度は解説ACです…
あと典型90問は2問しか解いていなくて(どちらも★2)、精選100問は30問くらいやっていました。まぁまだどちらも本腰入れて取り組んではいなかったです。

習得していたアルゴリズム/データ構造

(多分)しっかり理解しているやつら

• 全探索
• bit全探索
• 順列全探索
• BFS(幅優先探索)
• ワーシャルフロイド法
• std::map/std::set
• std::deque
• std::queue
• std::priorty_queue

一応理解しているやつら(下にいくほど怪しい)

• DFS(深さ優先探索)
• DP(ナップザックDP程度)
• 貪欲法
• 半分全列挙
• 累積和(一次元,二次元)
• ダイクストラ法
• 二分探索
• 尺取り法

こんなところでしょうか…？挙げ忘れているものがある気もしますし、挙げているものでコンテスト中に使えるか定かでないものも割とある気がします。
ただ緑になるうえで、ダイクストラ法やワーシャルフロイド法、半分全列挙を学ぶ必要は特にない気がしますね…基本的なアルゴリズム/データ構造をないがしろにしたまま高度なアルゴリズムを学んでも、実際のコンテスト中にそれを使用する問題までたどり着けないです。あと出る頻度が(DPなどと比べると)少ないので、レートへの還元という観点で見るとコスパが悪い気がします。

レートを上げるためにやったこと、やるとよさそうなこと

※私がARCに一切参加していないため、ここで書いている内容もARCを度外視しています。

0-200程度まで

APG4bやアルゴ式で多次元配列とか多重ループの書き方まで習ったら、あとはABCのA問題、可能ならB問題を多く解くといい気がします。とにかく実際の問題をACしまくることで文法に慣れつつ、できれば解説なども見てSTLの使い方や典型テクニックを学ぶとあっさり抜けられると思います。書いてから思ったけど、このレート帯の人がわざわざこんな記事見る？
この頃の私はdiffが低い(10付近?)A,B問題を適当に少しずつ解いていたはずです。STL及び関数のことを全然理解していない³くらいの頃だったので、一問一問の実装にかなり時間がかかっていました。(今思うとなつかしい)

200-400(茶色)まで

ABCのB問題(余力あればAも)を100問くらい解いて、ある程度速解きができるようになっておくといい気がします。大体B問題までを0ペナ10分以内で解けるとパフォの安定感が高まりますし、C問題が難しければ十分に茶パフォが出るので、結構大事です。毎回それができるなら、一応入茶できるはずです。
私が入茶したときは全探索とbit全探索と順列全探索、std::map,std::setくらいしか使えませんでしたが、なんとかなりました。茶色になるまではアルゴリズムがどうのというより、とにかく問題を解くのが有効だと思います。強いて言えば、std::map,std::setは使えるようになっておくと便利です。

↑ 点が多い方のグラフはACした問題の総得点の推移らしいですが、これを見ると入茶前に頑張った結果、レートの伸びが結構良くなったことが窺えます。

入茶した回のC問題は運よくbit全探索とstd::mapで解ける問題だったので速解きできました。本当に運が良かったです。

400-800(緑色)まで

ここからはちゃんとアルゴリズムなどを学ばないと停滞すると思います。このレベル帯で特に習得すべきアルゴリズムは以下の5つだと思います。

• DP(部分和問題、ナップザック問題が解ける程度)
• 二分探索
• DFS(深さ優先探索)
• BFS(幅優先探索)
  (BFSに付随してstd::queue, std::deque, std::priority_queueも習得しておくといいかもしれません)
• 累積和

私はDPに強く苦手意識を持っていたのでしばらく逃げていましたが、レート500台になってからいざ再勉強してみるとそこまで苦労せず習得できました。D問題は大体DPと言わんばかりの出題率なので(体感です)、とにかく早くDPは習得するべきです。
二分探索も、DFS,BFSと同列かそれ以上に出題率が高く重要なのですが、私は二分探索はどうも習得できませんでした…(今なおできません)std::lower_boundなどならできるのですが、自力で二分探索の実装をするといつもバグらせてしまいます。ただし、逆にいえば二分探索が苦手でも入緑は可能ということです。おそらく、上の5つのアルゴリズムのうち3つくらい習得しておくと大丈夫な感じです。

あと、上のアルゴリズムのうちなにかしら一つでも十分に使いこなせるもの,得意なものを持っておくと強みになりやすいです。得意なアルゴリズムが出題された回に限りますが、速解きしたり、普段は解けないようなD,E問題まで射程に捉えたりできます。
私はBFSが書きやすくてかなり好きなので、BFSを使う問題には積極的に挑戦していました。実際、入緑した回のコンテストではC問題とE問題がBFSを適用できるようになっており、そのおかげで5完できました。その前の回でも、BFSのおかげで初めてコンテスト中にE問題をACすることができましたし、さらにその4つ前の回でもD問題をACできました。入茶のときに続き、得意な範囲が出題されたのは運の良さとしか言えないのですが、それはそうとして得意なアルゴリズムを持つことは非常に効果的であることを実感させられました。

あとはレート400-500くらいの時期にAtCoder ProblemsのBoot camp for BeginnersのEasy 100を埋めました。基礎力が結構固まり、B問題までの速解きを安定させてくれたように感じます。まぁこれは入茶するまでにやるのが一番効果的な気もしますが、入茶した後でもやっていない人はやる価値があると思います。

共通事項

レートを上げたいなら問題をたくさん解こう！結局これに限ります。(数学がとても得意なら話は別かもしれませんが…)解く問題は自分のレート±200くらいのdiffが適切かな…？

緑コーダーになった感想

競プロを始めてから1年7ヶ月、コンテスト初参加からは15ヶ月くらいでなれたわけなので、「やっとなれた」という感想がふさわしい気はしますが、どちらかというと「もうなった」感のほうが強いです。まぁ入茶するまでに9ヶ月、レート500に到達するまでに3ヶ月、それからレートの伸びがよくなって4ヶ月で入緑できたので、伸びのペースを考えると当然な気もします。

記念すべき入緑回となったABC277ですが、水パフォを出せると入緑できることを事前に知り、過去最高級に緊張していました。今まで水パフォなんて一度も取ったことないくせに、なぜそこまで緊張していたかはわからないです。ただ、この普段以上の緊張がいい感じに集中力を高めてくれた気がします。C問題まではかなり速解きが成功したうえ、D,E問題でも落ち着いて実装の指針を立てることができたのが良かったです。E問題を解けたときは喜びのあまりガッツポーズして叫んでいました。⁴

まぁそんなこんなで思わぬタイミングで入緑を決められたわけですが、入緑しましたツイートが想像より遥かに反応をいただけたことにも驚きました。たくさんのリプも頂きましたが、私はリプ返がかなり下手なので嬉しい悲鳴をあげていました。競プロ界隈が温かいという話はよく聞きますが、それを強く実感させられました。

さいごに

競プロを始めてから割と目標にしていた入緑を達成できたのはとても嬉しいですが、どうせならもっと頑張って水色コーダーを目指したいと思っています。多分水色まではギリギリ到達できると思っていますが、そこからは伸ばせる自信がないので、そのときは今ほどの意欲はなくなる気がします。まぁ水色になれるのが何ヶ月後かはわからないですし、何ならなれない可能性も十分にありますが、ここまでこれたのできっと大丈夫でしょう。(適当)
今はどちらかというと、これを書いた直後に茶色に落ちないかが心配です。直近2回のコンテストはBFSが刺さったのでいい成績を出せただけな気はしますし、何しろこの記事を書いた翌日にはポケモンの新作が発売するので必然的に競プロにあてる時間が大幅減少します。ただでさえ最近スプラトゥーン3に没頭していたので、腕が落ちていて即入茶はありえそうな話です。一度落ちたら中々戻ってこれない気がするので、そうならないよう気を付けます…

ここまでお読みいただき、ありがとうございました！

1. 寿司打の5000円コースで5080円お得が出せるくらいです。2年くらいやってた割には遅いような気もしますが、日常生活で不便しない速度なので満足しています。 ↩

2. 部活は週4で2時間弱あります。この頃は部活以外で競プロに触れていなかったので、本当に1週間くらいかけないと理解できなかった、ではないはずです… ↩

3. 特に返り値の概念が分かっていなかったです。例えばstd::reverseは与えた文字列にそのまま加工してくれるのに、std::stoiはint型のコピーを渡してくるのが意味不明でした。その結果std::stoiは使えないやつと思い込み、敬遠していましたね… ↩

4. コンテストでは感情が非常に揺れ動くので、割とこれは平常運転だったりします。 ↩