こんにちは。こんばんは。AtCoderユーザーのRuteと申します。
先日のAtCoder Beginner Contest 203（Sponsored by Panasonic）で
私は、AtCoder緑Ratingに到達いたしました。
茶Ratingに到達したのが2019年12月23日のことですから、実に1年と5ヶ月以上かけて緑Ratingに到達した、ということになります。
入緑しました！！！！！！！やったー！！
— Rute(リュート)🚲📈⌨️🌸🍓 (@rute_not_route) May 30, 2021
RuteさんのAtCoder Beginner Contest 203（Sponsored by Panasonic）での成績：1108位
パフォーマンス：1409相当
レーティング：707→800 (+93) :)
Highestを更新し、6 級になりました！#AtCoder #ABC203（SponsoredbyPanasonic） https://t.co/dnjHJcZiuP pic.twitter.com/1gz8DA4GUc
当日は皆さんから多くのメッセージをいただきました。本当にありがとうございます。
この記事では、主に茶Rating(400~799)の方、灰Rating(0~399)の方をターゲットとして、緑Ratingに上がるための戦略などをお伝えしたいと思います！！
注意：この記事はあくまでも個人見解であるため、一般論と異なる場合があります。その点ご了承下さい。
1.はじめに~そもそも緑Ratingとは~
現在、AtCoderのアクティブユーザーの数はおよそ81000人で、その中におけるRating800の順位は2021/05/31時点で14671位でした。
従って、上位18.1%の位置の成績となっています。
競技プログラミングにおいては初級者を脱出して、中級者になったというレベル感です。
2.緑Ratingに到達した時点の記録
2.1 コンテスト別正解率
| コンテスト | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| ABC | 100.0% | 100.0% | 79.3% | 26.6% | 10.3% | 0.0% |
| ARC | 89.3% | 32.0% | 28.1% | 3.3% | 0.0% | 0.0% |
| AGC | 55.8% | 1.9% | 0.0% | 0.0% | 0.0% | 0.0% |
(2021/05/31時点、Rute-AtCoder Problemsより取得したデータ)
この正解率を見ると、AtCoder Beginner ContestではA問題・B問題を全問ACすることは当たり前で、C問題についてもほぼ8割の正解率となっています。
AtCoder Regular ContestではA問題の正解率が9割と高いですが、B問題以降の正解率はそれほど高くありません。
AtCoder Grand ContestではA問題の正解率は高々5割程度で、B問題以降はほとんど正解していません。
2.2 色別正解率
| 灰 | 茶 | 緑 | 水 | 青 |
|---|---|---|---|---|
| 99.2% | 86.2% | 39.8% | 6.2% | 1.8% |
(2021/05/31時点、Rute-AtCoder Problemsより取得したデータ)
灰色Difficultyの問題はほとんど正解していて、茶色Difficultyの問題も8割以上正解しています。
緑Difficultyの問題は約4割の正解率となっています。
以上のことから
- ABCは,A問題,B問題を中心に正解し、C問題も正解する
- ARCはA問題を正解し、B問題・C問題は出来る問題を正解する
- AGCはA問題を正解する。B問題以降は難しいので飛ばして良い
- 灰色・茶色Difficultyの問題を積極的に埋める
ということにより緑Ratingに到達していることが分かります。
(精進量はあくまで個人の技量などによりますので、あまり信じすぎないようにお願いします)
2.3 Rated Point Sum / AC数
2021年6月6日時点で
AC数が1026AC
Rated Point Sumが147500でした。
E869120さんの記事によると、
1100 問解けば 90% の人が水色コーダーになれます。ということだったので、今後も問題を解いて1100ACを目指したいと思います。
3.入緑するために必要な知識・戦略など
緑Ratingは、Chokudaiさんのブログで説明されている通り、「運だけで到達することはまず出来ないライン」です。
そこで、緑Ratingに到達するために私が競技プログラミングでとった戦略や、知識などについて共有を行います。
3.1 『早解き』力の向上
主にこれは灰Rating(0~399)から茶Rating(400~799)の方にとって有効な戦略かと思いますが、
コンテスト中において『早解き』を行うということです。
(後述しますが、私がRatingを上げたのはこの『早解き』がほとんどだと思っています。)
競技プログラミングでは、上位の順位になるためには点数と所要時間の早さが要求されます。上位の順位を取る事で、パフォーマンスの値は高くなります。これにより、Ratingを容易く上昇させることが出来ます。
(パフォーマンス：コンテスト1回ごとに計算されるRatingを指します)
初心者向けコンテスト、AtCoder Beginner Contestでは最近D問題以降の問題の難易度が、前半3問の難易度よりもはるかに難しい、という状況が続いています。
(最近のコンテストでこのような傾向があるので、運営が修正を行う可能性があります)
このような傾向の問題セットでは、3完早解きを行うことによりコンテストの順位を上げることが出来ます。
過去に行われた「3完早解き型」の問題セットのDifficulty・及び3完時間別のパフォーマンスをまとめると、以下のようになります。
Difficulty
| コンテスト | A | B | C | D | E | F | (D-Diff)-(C-Diff) |
|---|---|---|---|---|---|---|---|
| ABC203 | 6 | 12 | 168 | 1622 | 1750 | 2252 | 1454 |
| ABC201 | 4 | 16 | 204 | 1317 | 1694 | 2484 | 1113 |
| ABC199 | 5 | 36 | 436 | 1804 | 1814 | 2065 | 1368 |
3完パフォ
| コンテスト | 最速 | 10分 | 20分 | 30分 | 50分 | 最遅 | (最速-最遅) |
|---|---|---|---|---|---|---|---|
| ABC203 | 1466 | 1388 | 935 | 703 | 463 | 246 | 1220 |
| ABC201 | 1268 | 1256 | 1162 | 1042 | 857 | 551 | 717 |
| ABC199 | 1595 | 1522 | 1210 | 1022 | 824 | 583 | 1012 |
単純に$X$ = (最速-最遅)/(D-Diff-C-Diff)
と定義して計算するとこのようになります。
(これは興味本位で計算した値で、$X$自身の意味はあまりないものと考えています)
| コンテスト | $X$ |
|---|---|
| ABC203 | 0.839064649 |
| ABC201 | 0.644204852 |
| ABC199 | 0.739766082 |
| 平均 | 0.741011861 |
従って、C問題とD問題のDifficultyの差が大きくなれば大きくなるほど$X$の値は増加するのではないかと仮定することが出来ます。
これにより、「3完早解き」の問題セットでは早解きがいかにパフォーマンス値を上げる為に有効かが分かっていただけたと思います。
3.2「『早解き』力」を向上するためには
さて、このような早解き能力はどのようにすれば向上するかですが、
6月2日に放送されたAtCoderの公式放送、「あーだこーだー」内でE869120さんがお話されていた内容を引用すると、
- 問題文で問いたいことを理解する力を付ける(できれば各問題1分くらいで)
- コードをバグらせずに実装する力を付ける
- 全探索・ソート・二次元配列など、約20個の典型を身につける
ということが挙げられています。
1番目については、コンテストに多く参加したり過去問を解くことで身につくと思います。
2番目については、解いたことのある過去問をもう一度解くこと等で身につくと思います。簡単な問題でもバグらせてしまうとパフォーマンス低下につながりかねないのでこれは大事です。
3番目について、
- ABC203-C問題でソートの知識
- ABC201-C問題で全探索に関する知識
- ABC199-C問題で文字列処理に関する知識
が出題されています。これらの問題を早解きすることによりパフォーマンスを大きく上昇させることが出来ます。
所詮早解きなので、本来の実力とは大きくかけ離れたパフォーマンスとなる場合が多いです。ただ、その時にレーティングを大きく上げることが出来る、というのは本当に気分が良いことだと思うので、早解きで高パフォーマンスを狙ってみて下さい！！
3.3 アルゴリズムはあまり必要ない
Rute自身、実際Ratingを上げたのはほとんどが早解きによるものでした。
そのため、アルゴリズム的な知識は実はこれくらいで十分でした。
特に重要なものは太字で示します
- 全探索(単純なもの・工夫するもの)
- Bit全探索
- 順列全探索
- 累積和
- 動的計画法(簡単なもの)
- 隣接行列
- ソート(イベントソートを含む)
- いもす法
- 二分探索
- しゃくとり法
- 貪欲法
これだけのアルゴリズムを勉強して、あとは早解きをすることによって、緑Ratingに到達することが出来たのです。
一部記事で幅優先探索や深さ優先探索が緑Ratingに到達するのに必要、と書かれていたりしますが、極端な話"早解き"能力さえあればこういうアルゴリズムを勉強しなくても緑Ratingに上がることは出来ます。
ただ、早解き型になっていないコンテストでは速く問題を解いたとしても低いパフォーマンスを取得してしまうことがあるので、早解き以外の能力も必要であると感じます。
早解き以外に行った戦略について説明します。
コンテスト後解けなかった問題を解く
これは、コンテスト本番に解けなかった問題について
- どの部分の考察が足りなかったか
- どのようなアルゴリズムを用いると解くことが出来るのか
ということを認識するために行っています。
(目安としては私の場合水Diffまでです)
コンテスト終了後公開される公式解説を見て、問題の解法等について理解します。
初見の問題に慣れる
「くじかつ」や「あさかつ」と呼ばれているコンテストが、定期的にAtCoder Problems上で開催されています。
これらの問題の中には、当然「解いた事がない、初見の問題」も含まれるので、コンテスト本番同様に問題について未知の状態から解く、ということを行っています。これらについても解けなかったら前述している通り解けなかった問題についての解説を理解できるまで見ます。
これ以外にも、様々な戦略があると思います。
例えば、Twitter等で問題について質問をするということも有効です。
(灰色/茶色ユーザーが青・黄色などABC Rated上位のユーザーなどに質問をすると、難しい問題で無い限り回答してくれる、と思っています。)
4 最後に
最近、ユーザーのレベルのインフレが進み、茶Rating→緑Ratingへの上昇が難しくなっているように感じます。Ratingの上昇を希望するなら、やはり「早解き」というものは有効です。ただ、これはあくまで個人的な意見ですから、確実にアルゴリズム力をつけたい方はけんちょん本やPAST本などをはじめとする競技プログラミング対策本や、Qiita,はてなブログ等に掲載されている解説記事、それからYouTubeなどにアップロードされている解説動画などを見ることをお勧めします。
最後に宣伝にはなりますが、私自身もYouTubeチャンネルにて
競技プログラミングの過去問の解説動画をアップロードしております。
Ruteチャンネル
Ruteチャンネルでは主にA問題・B問題への解説動画の投稿を行っており、
競技プログラミング初心者に分かりやすい動画制作を心がけております。
毎回のABC級コンテスト終了後には、
コンテストの問題の解説を含めた「振り返り配信」を行っています。
今回の記事で興味を持った方はこの機会にチャンネル登録の方もお願いします。