【AtCoder】緑色になるまでにやったこと【必要なスキル・目安】 #C++

記事の内容

プログラミング言語は C++ を想定していますが、異なる言語でも通用する内容です。

まず、AtCoder で緑色になるための目安を示します。
以下の 2 点を継続的に達成しており、AtCoder Beginner Contest (ABC) にほぼ毎回参加していれば、初参加から半年ほどで緑色になるはずです。

AtCoder で緑色になるために必要なスキルのうち、優先度が高いもの挙げます。
これらをおおよそ理解しておけば、ほとんどの ABC において、A 問題から C 問題までを 20 分以内に AC できます。

プログラミング言語は C++ を想定していますが、異なる言語でも同様のライブラリやデータ構造があります。

プログラミング言語・データ構造など

アルゴリズム

ABC において、C 問題までは vector、set (unordered_set)、map (unordered_map) などを上手く使うだけで解ける問題も多いので、データ構造やライブラリを知っておくことは重要です。知らなければ、そもそも解法を思いつけないこともあります。

bit 全探索、幅優先探索、ダイクストラ法など、最初は混乱するかもしれませんが、一度覚えてしまえば難しくないです。ある程度の量の問題を解けば、考えなくてもスラスラ書けるようになります。仕組み自体は難しくないので、慣れることが大事です。

AtCoder で緑色になるために知っておくとよいスキルを挙げます。
知らないと緑色になれないとまでは言えませんが、以下に挙げたことの基本的な部分を知っていると楽です。
これらをおおよそ理解しておけば、ABC において、D 問題や E 問題を解けることが増えます。

Union-Find は簡単で便利です。コードを見れば、何が起きているのか理解できますし、すぐに習得できます。

いもす法は発展的なパターンは難しいですが、基本的なパターンは習得できます。

ワーシャルフロイド法とクラスカル法はダイクストラ法などと同様に、最初は混乱するかもしれませんが、一度覚えてしまえば難しくないです。仕組み自体は難しくないので、慣れることが大事です。

$\text{mod}$ 関連は完全に理解はしていなくても、べき乗や逆元を求めるコードを準備しておくとよいです。

AtCoder で緑色になるために必ずしも知らなくてよいスキルを挙げます。
無論、緑色になったあとには必要になるので、知っているに越したことはですが、難しければ現時点では習得していなくても緑色になれるという意味です。

動的計画法は今後のために知っておくべきですが、仮に動的計画法を使う問題を 1 問も解けなかったとしても、緑色になれます。実際、筆者は緑色になるまでに、コンテスト中に一度も動的計画法を使う問題を解いていません。
動的計画法はさまざまなパターンがあり、難しいです。少しずつ習得するのがよいと思います。

コンテスト中にコピー&ペーストするための自作ライブラリやコードを省略するための記法は使わなくても緑色になれます。

AtCoder Library (ACL) は使わなくても緑色になれます。

AtCoder で緑色になるまでに、筆者が実際にやったことを紹介します。

以下の記事に掲載されている記事をすべて読み、例示されている過去問をすべて解きました。
例示されている過去問は計 180 問ほどあります。

このほかには、特に何もしていません。