こんにちは、サトピンです。
久しぶりの投稿記事になります。
今回は、Atcoderで茶色になったので入茶するまでにしたことを書きます。8月の終わりごろからコンテストに参加し始めて、11/19のABC278で入茶しました!!
本記事の対象者
- 競技プログラミング初心者
- Atcoderで灰色Rate(rating:1-399)の方
自己紹介
- 2022年3月に国立大法学部を卒業
- 来年の4月から情報系の大学院に進学予定
- 競プロをはじめる前はweb系のプログラミングを1年弱やっていた。
- 大学でアルゴリズムの講義を受講したことはない。
といった感じです。
茶色になるために必要なこと
入茶するにはプログラミングと高校数学がある程度できる必要があります。競プロerには1,2回コンテストに出場して茶色以上のRatingを叩き出す人がいますが、彼らは情報系(または関連分野)でプログラミングをやってきたか、高校、大学で数学をガッツリ勉強しているか、Atcoder以外で競プロの経験があるか、あるいはその全ての経験があります。いずれにも当てはまらない場合は、
- プログラミングの基本文法(for文,if文,標準入出力など)
- 教科書レベルの高校数学
は最低限身につける必要があります。
以下、必要になるプログラミング・数学について掘り下げて説明していきます。
プログラミング
プログラミングをやったことがある方は好きな言語を使えばいいですが、未経験の場合はc++、次点でPythonをおすすめします。c++はAtcoderがapg4bという学習サイトを開設しており、ここで競プロで必要な文法をある程度マスターできるからです。また、公式解説でc++のコードがあげられており学習コストが圧倒的に低いです。
Pythonも多くのユーザーに使われており、コード量が少ない、ユーザーの解説記事が多いといった点でおすすめです。
以下、apg4bのリンクです。
数学
Atcoderでは幾何、数列、整数といった高校数学の問題が偶に出題されるため、高校数学に苦手意識がある方は勉強することをおすすめします。少なくとも、茶色になるにはΣ、最大公約数(GCD)、素因数分解、約数の知識は持っておく必要があります。これらが問題に当たり前のように出てくるので知らないとそもそも問題の意味すら理解できないことになります。高校数学に不安がある場合は、以下のサイトを見ることをおすすめします。
高校数学の美しい物語はガッツリ数学の内容ですが、高校数学をわかりやすく解説しているので高校数学の勉強におすすめです。
私がやったこと
ここからは、私が入茶するまでにやったことを重要度が高いと思う順に紹介していきます。
コンテストに出場
コンテストに出ることは強く推奨します。勉強不足であるとしても、最初の10回はRatingが上がりづらいため、茶色になるには積極的にコンテストに参加する必要があります。ちなみに、私は13回目のコンテストで茶色になれました。
入茶の目安としては、初回から10回連続で600パフォ以上を出せば茶色になれます。そうでなくても、600以上を出し続ければ入茶できる可能性はかなり高まります。なので、茶色になりたいという方は600パフォ以上を一つの目標にするといいです。
パフォーマンスについては以下の記事が参考になります。
過去問
一番役に立ったのは、直近のコンテストで出題された過去問です。
入茶するまで解いたAtcoderの問題数は365問です。しかし、後に紹介する競技プログラミングの鉄則やアルゴ式でも問題を解いているため、実際に解いた問題数はもっと多いです。
これはA問題からF問題で、それぞれの問題ごとに解いた数を表しています
これはdifficulty(以下、diffとします。)ごとに解いた問題数です。
diffとは、本番中に半分の人がACできたRatingを表します。
中にはA・B問題の過去問を全て解く人もいますが、そこまでする必要はありません。慣れるために灰diffの問題を解くのは有効ですが、自分のレートより小さいdiffの問題を解いても効果は薄いです(苦手な問題であればその限りではありません)。また、かなり前のコンテストだと現在と傾向が異なることがあるので、解くのであれば最近開催されたコンテストの問題を解くことをおすすめします。
慣れてきたら、灰色上位diff(Rating:200-399)や茶diffの問題を解くことをオススメします。特に、茶diffは茶色の半分以上が解ける問題で、安定して解けるようになれば、入茶に大きく近づきます。私は直近3回のコンテストで茶diffまでの問題を解ききり、入茶することができました。
Atcoder Problemsでは、Atcoderの全過去問のリンクが掲載されており、diffを見てから問題を解くことができます。
競プロ典型90問(難易度☆2と☆3)
競プロ典型90問(以下、典型90とします。)も典型問題を抑えるのにいい教材です。典型９０は鉄則本の筆者(E869120さん)が出題したコンテンツで、初心者から上級者までを対象にしています。私は難易度☆2(灰diff相当)と☆3(茶diff相当)を解きました。初心者にとっては難しい問題が多いですが、解説ACをするだけでもかなり力がつくと思います。
競技プログラミングの鉄則
競技プログラミングの鉄則(以下、鉄則本とします。)は典型アルゴリズム(累積和、二分探索など)を履修するのに役立ちました。 また、競プロの考察テクニックも掲載されており、アルゴリズムを勉強するだけでは解けない問題も解けるようになりました。
累積和、二分探索がわからない方はネット記事だと以下が参考になります。
アルゴ式
アルゴ式も活用しました。
特に、全探索、ビット演算の勉強で役立ちました。アルゴ式は、動的計画法(以下、DPとします。)部分の教材が豊富なのでDPの学習でも活用していきたいです。
勉強したアルゴリズム
| アルゴリズム | 習熟度 | 重要度(高・中・低) |
|---|---|---|
| 全探索(for文) | A | 高 |
| Bit全探索 | B | 高 |
| 順列全探索 | A | 高 |
| 二分探索 | A | 中 |
| 尺取法 | C | 小 |
| STL(データ構造) | A | 高 |
| GCD | A | 高 |
| 素数判定 | A | 高 |
| 約数列挙 | B | 高 |
| 素因数分解 | B | 高 |
| 累積和 | B | 中 |
| いもす法 | C | 小 |
| グラフ(隣接リストなど) | A | 高 |
| DFS | A | 中 |
| BFS | B | 中 |
| メモ化再帰 | B | 中 |
| DP(茶diff程度) | C | 中 |
| 座標圧縮 | C | 小 |
| Union-Find | A | 中 |
習熟度については、
A： 本番中に解いたアルゴリズム
B： 本番で解いたことはないが、実装したことがあるアルゴリズム
C： 実装したことはあるが、理解度が微妙なアルゴリズム
重要度の認識としては、
高：入茶に必須
中：茶diffで出題されることが多く、解けたら有利
小：灰色時点では解けなくても大丈夫そう
といった感じです。
注意：これは2022年の記事です。現在では必要なアルゴリズムや重要度が変わっている可能性があるため、参考程度にとどめてください
おわりに
入茶するまでに3ヶ月かかりました。本番中に問題が解けずに悔しかった時もありましたが、ここまでやってこれてよかったです。そして、入茶したときにフォロワーさんから「おめでとう！」のたくさんのメッセージがもらえて本当に嬉しかったです。また色変記事が書けるように頑張ります。
追記：他の方の色変記事を見たい場合、以下のリンクから好きな記事を閲覧することができます。