AtCoderで緑色から水色に上がるには何を勉強すればよいか

コンテストに参加しはじめた時には300パフォみたいな時期もありましたが、そこから7ヶ月かけて水色に到達しました。競技プログラミングの世界には明らかにエンジンが違う天才のような人もいますが、おれはそうではなく努力型です。自分なりにどうやって勉強すればよいか考えて努力を続けてきました。

なので、きっと多くの人にとって役に立つことが言えるはずです。

水色になるにはABCでEまでとる力が必要

最近のAtCoderではABCのEまではとらないと水色に上がるのは難しくなっています。おそらく今後もどんどん難しくなっていくはずです。それは、道が整備されているからというのもありますし、やる気のある人が増えはじめているからです。

4完早解きでもそれなりのパフォは出ることがあるため、これを継続することで水色に上がれる可能性もゼロではないと思いますが、競技プログラミングへの参加をアルゴリズム力を高めるためと考えた場合には早解きには価値はなく、時間がかかっても問題をしっかり解けることを目指すべきです。特に、水色くらいでは、アルゴリズム力を高めることを重視すべきです。

おれは低レート帯での早解きは反対派です。

水色直前で止まる人の特徴

実際に、水色直前でずっと止まる人の特徴としては、 Eがとれるというのはまぐれというレベルの場合が多いです。

そういう人の特徴は、普段は4完か、場合によっては3完しかとれないけど、たまに上位コンテストで良いパフォをとって爆裂に上げてレートを上げる（もちろん、逆に運ゲーに負けて大幅に下げることもある）というもので、実力的には緑中盤程度というものです。

おれはこのやり方は、本質的ではなく時間の無駄なので、やめた方が良いと思います。ギャンブルと変わりません。

以上より、この記事では、 ちゃんとEまでとれるようになって水色になることを目指します。

問題をきちんと解いて上に上がるという方針は、茶色から緑色に上がる時と同様です。

彼らはなぜEがとれないか？

ABCのDとEの間には難易度にかなりの差があります。レッドコーダーなど、高みにいる人からみると、どちらもゴミレベルに見えるかも知れませんが、下から上がっていく場合には、DはとれてもEはとれないという時期が長く続きます。

難易度に飛躍があるからです。 EからFはさらに飛躍があります。おれは水色に上がりましたが、ABC全完は一度もありませんでした。しかしほとんどは5完してました。

ABCのD-E-Fの難易度上昇の急激さとABCとARCの間の難易度差は、 AtCoderが持つ問題の一つだと考えています。以下の記事では、緑色と水色の境界で止まる人が多い原因になっているという分析をしました。

AtCoderで水色に昇格しました！！！

Eのそびえ立つ壁の前にやる気をなくし、正攻法で解くための勉強をせず、とにかくDまでの早解きで最低限のレートを確保して、 Eに対しては自己流で挑み続けるというのが、Eが解けるのがまぐれの人たちの特徴です。

Eの問題は、たまに、自己流でゴリゴリやると解けてしまうような問題が出ます。また、C++ならば計算量が不利でもぎりぎり解けてしまうというものも存在します。

おれは緑色から水色に上がれない人の特徴を探るためにそういう人のコードを読んだのですが、ACしている場合でもコードが混乱していてすっきりしていないことが多いです。

想定解法で解けるようにしよう

では何をすべきかというと、自己流ではなく、用意された想定解法で解けるようになるというのが Eを安定して解けるようになるためにやることです。そしてこれこそが、緑色から水色に上がるための王道です。

このレベルでは多くの問題では、紙の上で正しい考察が出来ていないと解けないことが多いです。数え上げのような問題では、式変形が必要になる場合もあるでしょう。グラフ問題に帰着させて整理するときれいに解けるものもあります。

ですから、Eがまぐれな人たちは、少しだけWAしたとか、いくつかのケースがTLEしたということを繰り返すのです。それは、正しい考察が出来ておらず、穴があるから起こるのです。

Dまでは解ける人であれば多くの人が、解法を見たあとならばEの解法ACならば出来るでしょう。 FだってAC出来るはずです。実装力は問題ではないことがほとんどなのです。

問題は解法の考察力です。

どうすれば想定解法で解けるようになるか

範囲：蟻本のほぼすべて

基本的にEでは、競技プログラミングのほとんどのテーマが出題されますし、発展的なものでなければ知識は持っておいた方が良いと思います。蟻本の中級編までと、上級編の一部については範囲です。まず扱われないテーマは挙げることが出来ますが、全体からすると一部です。トポロジカルソートなども見たことがあると思います。

ライブラリについてですが、例えば、AtCoderのABCはセグ木がなくても解ける問題が多いですが、あった方が考察もコードもすっきりします。 HL分解、ウェーブレット行列、Treap、高速FFTなど発展的なトピックも知ってると有利になることはありますから、アルゴリズムの勉強の一貫として知っておいてもよいでしょう。

ただ基本的には、累積和、優先キュー、Ordered Set、二分探索など基本的な要素を組み合わせて解くものが多いです。グラフでは、ダイクストラ法、ワーシャルフロイド法、クラスカル法などの応用問題を時々みます。最大流問題もあったと思います。木に関する問題は、ゲーム含め出まくります。

二分探索については、抽象化フレームワークを用意しています。たぶん一番使ってるライブラリではないかと思います。持っておくとよいでしょう。

二分探索アルゴリズムを一般化〜めぐる式二分探索法のススメ〜

おれの競プロライブラリです。rust-comp-snippet

精進は重要

大切なのは考察が出来ることと言いましたが、実際に勉強をする際には、紙の上で検討して解答を読んでおわりではなく、やはり実際にコードを書いてみるとより理解が深まることが多いです。おれは過去問の500点については2/3くらいは埋めています。他の問題は、実装しても学ぶことがないことが明らかだったので実装しませんでした。

勉強時間は1000時間は必要

おれは一年前くらいに無職になって、Rustで競技プログラミングをすることに決めました。自分にとって足りないものだと思ったからです。

他にも、ブログやユーチューブなどもやっていますから、全時間を競技プログラミングの勉強に注ぎ込めるというわけではないですが、コンテストへの参加と勉強時間を合算すると、 1000時間は超えていると思います。

おれはもともと目標がもっと上にあるため、若干オーバーキル気味の遠回りはしていますが、それは大半ではないでしょうから、 1000時間くらいは勉強しないといけないというのは事実だと思います。

ふつうの人間にとっては、 100時間とかちょろっとやって到達出来るものではないと思うので、諦めずに続ける必要があります。

この1000時間というのが長いと感じるか妥当と感じるかはわかりませんが、例を示します。

CSGOという競技系FPSでは、世界のトップティアにいる選手のゲームプレイ時間は平均で大体7000時間くらいです。当然それ以外にも色々やってるでしょうし、戦略について常に考えているでしょうから、実質的には1万時間はとうに超えているものと思います。

競技プログラミングはゲームに似ていますから、 1000時間というのは、その入口に到達するのに必要な時間としては妥当といえます。

AtCoder以外のコンテストに参加する

おれはCodeforcesとyukicoderには参加しています。 CFのレートは1563です。

これらのコンテストのよいのはまずCFについていうと、水色直前の人にとってAtCoderのABCのA-Cあたりはただの作業でバカバカしいだけなのでこんなもので6問中3問消費されることが腹立たしいだけなのですが、 CFのDiv2はCかDくらいの難易度のものから始まります。このようにスタートの難易度が高いこともあって、問題間の難易度上昇もABCに比べると緩やかです。問題は比較的典型的なものが多く、参加することによる学びも多いです。問題文が英語で、しかもライターがネイティブではないのか少し怪しい英語なこともあるのですが、英語力がそれなりであればそこまで不利になることはないです。水色直前の人たちにとっては、間違いなく出る価値のあるコンテストです。

yukicoderの問題も典型的なものも多いため勉強になるのと、 unratedなので気楽に参加出来るのが魅力です。また、問題が面白いと思った時にはLIKEをつけるシステムがあったりと、問題ライターへのリスペクトをシステム的に推奨している点にも好感が持てます。