～AtCoderで緑Ratingになりました～

こんにちは。こんばんは。AtCoderユーザーの<b>Rute</b>と申します。
先日の<a href = "https://atcoder.jp/contests/abc203">AtCoder Beginner Contest 203（Sponsored by Panasonic）</a>で
私は、AtCoder<font color="#008000">緑Rating</font>に到達いたしました。

<font color="#804000">茶Rating</font>に到達したのが2019年12月23日のことですから、実に<b>1年と5ヶ月以上</b>かけて<font color="#008000">緑Rating</font>に到達した、ということになります。
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">入緑しました！！！！！！！やったー！！<br><br>RuteさんのAtCoder Beginner Contest 203（Sponsored by Panasonic）での成績：1108位<br>パフォーマンス：1409相当<br>レーティング：707→800 (+93) :)<br>Highestを更新し、6 級になりました！<a href="https://twitter.com/hashtag/AtCoder?src=hash&amp;ref_src=twsrc%5Etfw">#AtCoder</a> <a href="https://twitter.com/hashtag/ABC203?src=hash&amp;ref_src=twsrc%5Etfw">#ABC203</a>（SponsoredbyPanasonic） <a href="https://t.co/dnjHJcZiuP">https://t.co/dnjHJcZiuP</a> <a href="https://t.co/1gz8DA4GUc">pic.twitter.com/1gz8DA4GUc</a></p>&mdash; Rute(リュート)🚲📈⌨️🌸🍓 (@rute_not_route) <a href="https://twitter.com/rute_not_route/status/1399002802324578309?ref_src=twsrc%5Etfw">May 30, 2021</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

当日は皆さんから多くのメッセージをいただきました。<b>本当にありがとうございます。</b>

この記事では、主に<font color="#804000">茶Rating(400~799)</font>の方、<font color="#808080">灰Rating(0~399)</font>の方をターゲットとして、<b><font color="#008000">緑Rating</font>に上がるための戦略</b>などをお伝えしたいと思います！！

<font color="#FF0000">注意：この記事はあくまでも個人見解であるため、一般論と異なる場合があります。その点ご了承下さい。

#1.はじめに~そもそも緑Ratingとは~
現在、AtCoderのアクティブユーザーの数はおよそ<b>81000人</b>で、その中におけるRating<font color="#008000">800</font>の順位は2021/05/31時点で<b>14671位</b>でした。
従って、上位<b>18.1</b>%の位置の成績となっています。
競技プログラミングにおいては<b>初級者を脱出して、中級者になった</b>というレベル感です。

#2.緑Ratingに到達した時点の記録
## 2.1 コンテスト別正解率

|コンテスト|A|B|C|D|E|F|
|---|---|---|---|---|---|---|
|ABC|<font color="red">100.0%</font>|<font color="red">100.0%</font>|<font color="red">79.3%</font>|26.6%|10.3%|<font color="blue">0.0%</font>|
|ARC|<font color="red">89.3%</font>|32.0%|28.1%|<font color="blue">3.3%</font>|<font color="blue">0.0%</font>|<font color="blue">0.0%</font>|
|AGC|55.8%|<font color="blue">1.9%</font>|<font color="blue">0.0%</font>|<font color="blue">0.0%</font>|<font color="blue">0.0%</font>|<font color="blue">0.0%</font>|
<font color="grey">(2021/05/31時点、Rute-AtCoder Problemsより取得したデータ)</font>

この正解率を見ると、AtCoder Beginner Contestでは<b>A問題・B問題</b>を全問ACすることは<b>当たり前</b>で、<b>C問題</b>についても<b>ほぼ8割</b>の正解率となっています。
AtCoder Regular Contestでは<b>A問題</b>の正解率が<b>9割</b>と高いですが、B問題以降の正解率はそれほど高くありません。
AtCoder Grand Contestでは<b>A問題</b>の正解率は高々<b>5割程度</b>で、B問題以降はほとんど正解していません。


## 2.2 色別正解率

|灰|茶|緑|水|青|
|---|---|---|---|---|
|<font color="red">99.2%</font>|<font color="red">86.2%</font>|39.8%|<font color="blue">6.2%</font>|<font color="blue">1.8%</font>|
<font color="grey">(2021/05/31時点、Rute-AtCoder Problemsより取得したデータ)</font>

灰色Difficultyの問題は<b>ほとんど正解していて</b>、茶色Difficultyの問題も<b>8割以上正解しています</b>。
緑Difficultyの問題は<b>約4割</b>の正解率となっています。

以上のことから

- ABCは,<b>A問題,B問題</b>を中心に正解し、C問題も正解する
- ARCは<b>A問題</b>を正解し、B問題・C問題は出来る問題を正解する
- AGCは<b>A問題</b>を正解する。B問題以降は難しいので飛ばして良い
- <b>灰色・茶色Difficulty</b>の問題を積極的に埋める

ということにより<font color="#008000">緑Rating</font>に到達していることが分かります。
<font color="grey">(精進量はあくまで個人の技量などによりますので、あまり信じすぎないようにお願いします)</font>
## 2.3 Rated Point Sum / AC数
2021年6月6日時点で
AC数が<b>1026AC</b>
Rated Point Sumが<b>147500</b>でした。
<a href = "https://qiita.com/e869120/items/eb50fdaece12be418faa#2-2-4-%E9%81%8E%E5%8E%BB%E5%95%8F%E3%82%92%E8%A7%A3%E3%81%8D%E3%81%BE%E3%81%8F%E3%82%8B">E869120さんの記事</a>によると、
<b>1100 問解けば 90% の人が<font color="#00C0C0">水色コーダー</font>になれます。</b>ということだったので、今後も問題を解いて<b>1100ACを目指したいと思います。</b>

# 3.入緑するために必要な知識・戦略など
<font color="#008000">緑Rating</font>は、<a href = "https://chokudai.hatenablog.com/entry/2019/02/11/155904">Chokudaiさんのブログ</a>で説明されている通り、「運だけで到達することはまず出来ないライン」です。
そこで、緑Ratingに到達するために私が競技プログラミングでとった戦略や、知識などについて共有を行います。

## 3.1 『早解き』力の向上
主にこれは<font color="#808080">灰Rating(0~399)</font>から<font color="#804000">茶Rating(400~799)</font>の方にとって有効な戦略かと思いますが、
コンテスト中において<b>『早解き』を行うということです。</b>

<font color="#808080">(後述しますが、私がRatingを上げたのはこの『早解き』がほとんどだと思っています。)</font>

競技プログラミングでは、上位の順位になるためには<font color="#FF0000"><b>点数</b></font>と<font color="#FF0000"><b>所要時間の早さ</b></font>が要求されます。上位の順位を取る事で、<b>パフォーマンス</b>の値は高くなります。これにより、Ratingを容易く上昇させることが出来ます。
<font color="#808080">(<b>パフォーマンス</b>：コンテスト1回ごとに計算されるRatingを指します)</font>

初心者向けコンテスト、<b>AtCoder Beginner Contest</b>では最近<b>D問題</b>以降の問題の難易度が、前半3問の難易度よりもはるかに難しい、という状況が続いています。
<font color="#808080">(最近のコンテストでこのような傾向があるので、運営が修正を行う可能性があります)</font>
このような傾向の問題セットでは、<b>3完早解き</b>を行うことによりコンテストの順位を上げることが出来ます。

過去に行われた「3完早解き型」の問題セットのDifficulty・及び3完時間別のパフォーマンスをまとめると、以下のようになります。


<b>Difficulty</b>

|コンテスト|A|B|C|D|E|F|(D-Diff)-(C-Diff)|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|ABC203|<font color="#808080">6</font>|<font color="#808080">12</font>|<font color="#808080">168</font>|<font color="#0000FF">1622</font>|<font color="#0000FF">1750</font>|<font color="#C0C000">2252|<b>1454</b>|
|ABC201|<font color="#808080">4|<font color="#808080">16|<font color="#808080">204|<font color="#00C0C0">1317|<font color="#0000FF">1694|<font color="#FF8000">2484|<b>1113</b>|
|ABC199|<font color="#808080">5|<font color="#808080">36|<font color="#804000">436|<font color="#0000FF">1804|<font color="#0000FF">1814|<font color="#C0C000">2065|<b>1368</b>



<b>3完パフォ</b>

|コンテスト|最速|10分|20分|30分|50分|最遅|(最速-最遅)|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|ABC203|<font color="#00C0C0">1466|<font color="#00C0C0">1388|<font color="#008000">935|<font color="#804000">703|<font color="#804000">463|<font color="#808080">246|<b>1220</b>|
|ABC201|<font color="#00C0C0">1268|<font color="#00C0C0">1256|<font color="#008000">1162|<font color="#008000">1042|<font color="#008000">857|<font color="#804000">551|<b>717</b>|
|ABC199|<font color="#00C0C0">1595|<font coloR="#00C0C0">1522|<font color="#00C0C0">1210|<font color="#008000">1022|<font color="#008000">824|<font color="#804000">583|<b>1012</b>|

単純に$X$ = (最速-最遅)/(D-Diff-C-Diff)
と定義して計算するとこのようになります。
(これは興味本位で計算した値で、$X$自身の意味はあまりないものと考えています)

|コンテスト|$X$|
|:-:|:-:|
|ABC203|0.839064649|
|ABC201|0.644204852|
|ABC199|0.739766082|
|平均|<b>0.741011861</b>|

従って、<b>C問題</b>と<b>D問題</b>のDifficultyの差が大きくなれば大きくなるほど$X$の値は増加するのではないかと仮定することが出来ます。
これにより、「3完早解き」の問題セットでは<b>早解き</b>がいかにパフォーマンス値を上げる為に有効かが分かっていただけたと思います。

## 3.2「『早解き』力」を向上するためには
さて、このような<b>早解き</b>能力はどのようにすれば向上するかですが、
6月2日に放送されたAtCoderの公式放送、「あーだこーだー」内で<a href = "https://qiita.com/e869120">E869120</a>さんがお話されていた内容を引用すると、

- <b>問題文で問いたいこと</b>を理解する力を付ける(できれば各問題1分くらいで)
- <b>コードをバグらせずに実装する力</b>を付ける
- 全探索・ソート・二次元配列など、<b>約20個の典型</b>を身につける

ということが挙げられています。
1番目については、<b>コンテストに多く参加したり過去問を解くこと</b>で身につくと思います。
2番目については、<b>解いたことのある過去問をもう一度解く</b>こと等で身につくと思います。簡単な問題でもバグらせてしまうと<b>パフォーマンス低下</b>につながりかねないのでこれは大事です。

3番目について、

- <a href = "https://atcoder.jp/contests/abc203/tasks/abc203_c"><b>ABC203-C問題</b></a>でソートの知識
- <a href = "https://atcoder.jp/contests/abc201/tasks/abc201_c"> <b>ABC201-C問題</b></a>で全探索に関する知識
- <a href = "https://atcoder.jp/contests/abc199/tasks/abc199_c"><b>ABC199-C問題</b></a>で文字列処理に関する知識

が出題されています。これらの問題を早解きすることにより<b>パフォーマンスを大きく上昇させる</b>ことが出来ます。

所詮早解きなので、<b>本来の実力</b>とは大きくかけ離れたパフォーマンスとなる場合が多いです。ただ、その時にレーティングを大きく上げることが出来る、というのは<b>本当に気分が良いこと</b>だと思うので、早解きで高パフォーマンスを狙ってみて下さい！！

## 3.3 アルゴリズムはあまり必要ない
Rute自身、実際Ratingを上げたのはほとんどが<b>早解き</b>によるものでした。
そのため、アルゴリズム的な知識は実はこれくらいで十分でした。
<font color="#808080">特に重要なものは<b>太字</b>で示します</font>

- <b>全探索(単純なもの・工夫するもの)</b>
- <b>Bit全探索</b>
- <b>順列全探索</b>
- <b>累積和</b>
- 動的計画法(簡単なもの)
- <b>隣接行列</b>
- <b>ソート(イベントソートを含む)</b>
- いもす法
- 二分探索
- しゃくとり法
- 貪欲法

これだけのアルゴリズムを勉強して、あとは<b>早解き</b>をすることによって、<font color="#008000">緑Rating</font>に到達することが出来たのです。
一部記事で<b>幅優先探索</b>や<b>深さ優先探索</b>が緑Ratingに到達するのに必要、と書かれていたりしますが、極端な話<b>"早解き"能力さえあれば</b>こういうアルゴリズムを勉強しなくても<font color="#008000">緑Rating</font>に上がることは出来ます。

ただ、<b>早解き型になっていないコンテスト</b>では速く問題を解いたとしても<b>低いパフォーマンス</b>を取得してしまうことがあるので、早解き以外の能力も必要であると感じます。

早解き以外に行った戦略について説明します。

### コンテスト後解けなかった問題を解く
これは、コンテスト本番に解けなかった問題について

- どの部分の考察が足りなかったか
- どのようなアルゴリズムを用いると解くことが出来るのか

ということを認識するために行っています。
(目安としては私の場合<font color="#00C0C0">水Diff</font>までです)
コンテスト終了後公開される公式解説を見て、問題の解法等について理解します。

### 初見の問題に慣れる
「くじかつ」や「あさかつ」と呼ばれているコンテストが、定期的に<b>AtCoder Problems上で開催されています。</b>
これらの問題の中には、当然<b>「解いた事がない、初見の問題」</b>も含まれるので、コンテスト本番同様に問題について<b>未知の状態から解く</b>、ということを行っています。これらについても解けなかったら前述している通り解けなかった問題についての解説を理解できるまで見ます。

これ以外にも、様々な戦略があると思います。
例えば、Twitter等で問題について質問をするということも有効です。
(灰色/茶色ユーザーが青・黄色などABC Rated上位のユーザーなどに質問をすると、難しい問題で無い限り回答してくれる、と思っています。)

#4 最後に
最近、ユーザーのレベルのインフレが進み、<font color="#804000">茶Rating</font>→<font color="#008000">緑Rating</font>への上昇が難しくなっているように感じます。Ratingの上昇を希望するなら、やはり<b>「早解き」</b>というものは有効です。ただ、これはあくまで個人的な意見ですから、確実に<b>アルゴリズム力</b>をつけたい方は<b>けんちょん本</b>や<b>PAST本</b>などをはじめとする競技プログラミング対策本や、Qiita,はてなブログ等に掲載されている解説記事、それからYouTubeなどにアップロードされている解説動画などを見ることをお勧めします。

最後に宣伝にはなりますが、私自身もYouTubeチャンネルにて<br>競技プログラミングの過去問の解説動画をアップロードしております。
<a href = "https://www.youtube.com/channel/UCvB4r-9OCn84AohIsnvLYhA">Ruteチャンネル</a>
Ruteチャンネルでは主にA問題・B問題への解説動画の投稿を行っており、
競技プログラミング初心者に分かりやすい動画制作を心がけております。
毎回のABC級コンテスト終了後には、<br>コンテストの問題の解説を含めた<b>「振り返り配信」</b>を行っています。
今回の記事で興味を持った方はこの機会に<b>チャンネル登録</b>の方もお願いします。