中一のwatasou1543です。ABC287で無事入緑しました。
はじめに
まず、私が競技プログラミングを本格的に始めたのは昨年の7月です。五月に一回コンテストに参加してみたのですが、
「言語って何？」
この状態でした。
ここから8か月で緑コーダーになることができました。
この記事では、入緑を目指している方のために、
・自分が入緑するまでにどんなアルゴリズムを学んだか
・どれくらい何をしたか
について書こうと思います。
学んだ言語
競技プログラミングでは、先輩から勧められたC++を使っています。また、今考えても競技プログラミングに最適な言語はC++だと思います。その理由は、
・ほかの言語よりも実行速度が速い
・解説が多い
・APG4bというサイトがあるので学びやすい(私もこのサイトでC++を学びました)
だと考えています。
Pythonをお勧めする方も多いですが、
・簡潔に書ける
・理解しやすい
反面、
・遅い(C++だと通りやすいのに...のような問題が時々ある)
・JOIの本選にはC++でしか出られない
といった問題があるので、私はお勧めしません。が、PythonをC++と併用して学ぶことで、
「Pythonだと2行で書ける！(例:ABC275-B)」
「C++だとすぐ解ける！(例:ABC276-C)」
といった問題にすぐ対応できます。なので、サブの言語としてPythonを持っておくと良いと思います。が、私はPythonが何もわかりません。
入茶するまでにやったこと
とりあえず、学んだアルゴリズムやデータ構造は以下のものです。
また、学んだアルゴリズムにランクづけをしています。
S:必須といってもいいレベル
A:重要
B:持っておくと便利
| アルゴリズム名 | ランク | 説明 |
|---|---|---|
| 全探索 | S | これがないとB問題も解けない。すべての基本。 |
| 累積和 | A | 区間の総和を$O(1)$で求められる。Cで頻出。 |
| imos法 | B | 区間に$O(1)$で数を足せる。Cで出る。 |
| bit全探索 | B | $O(2^N)$を全探索するアルゴリズム。大事。 |
| 二分探索 | A | $O(logN)$でソートされた配列から最頻値を求められる。最強。 |
| 繰り返し2乗法 | B | $N^M$を$O(logM)$で求められる。持っておいて損はない。 |
| DFS(深さ優先探索) | A | CはグラフのCという迷言?が生まれるほど最近C問題によく出る。再帰関数を使う。 |
| エラトステネスの篩 | A | $1$~$N$が素数かどうかを$O(NlogN)$で高速判定。素数問はDでよく出る。Cで詰まってこれを使ってD通してパフォーマンス爆盛り！とかできて強い。 |
また、この時は学ばなかったけど持っておきたかったアルゴリズムは以下の通り。
| アルゴリズム名 | ランク | 説明 |
|---|---|---|
| BFS(幅優先探索) | B | DFSとは違い、キューを使う。DFSよりもBFSのほうが実装は大変だが通る問題が多い。 |
| 順列全探索 | A | $O(N!)$を全探索できる。最近は減ったが、C問題でよく出ていた。C++が実装しやすい。 |
ちなみに私は茶色になるまでに461ACをして、20回Ratedでコンテストに参加しました。「AC数はレートに比例する」という考え方があるのですが、ACをして経験を重ねていくことが大事です。
入緑するまで
入緑するまでに以下のアルゴリズムを学びました。また、入茶するまでに必要なアルゴリズムはすべて完璧にしていることを前提にします。
| アルゴリズム名 | ランク | 説明 |
|---|---|---|
| DP(動的計画法) | A | 最も重要なアルゴリズムでかつ、応用が利きます。また、DはDPのDと呼ばれるほどDによく出ます。緑になるまでにEDPCなどを使ってちゃんと学習しておくことをお勧めします。 |
| ダイクストラ法 | A | 重みがある有向グラフの最短経路を$O(NM)$で求められる。 |
| ダブリング | B | 木の頂点iのk個上の頂点を$O(logk)$で求められる。 |
| ワーシャルフロイド | B | 重みが負の辺を含むグラフについての最短経路を$O(N^3)$で求められる。 |
| UnionFind | S | めちゃ大事。連結判定や閉路検出など、様々なグラフの問題で使え、実装もライブラリを持てば重くない。しかも$O(logN)$でできることが多い。私がグラフ好きな理由は多分これ。 |
| 約数列挙 | A | Dで素数関係が頻出。 |
ちなみに入緑するためにRatedで出た回数は31回、AC数は650です。
おわりに
ここまで目を通してくださり、ありがとうございます。ぜひ感想などを書いていただけると嬉しいです。
今は5月までの入水を目指して頑張っています。
もしかしたら記事を書くかもしれません。その時は目を通してくれると嬉しいです。
参考文献:
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】