はじめに
自分（工業大学出身のただのエンジニア）がAtCoderで茶色を目指す場合、何回コンテストに出る必要があるのか。一説によれば10回程度と聞くが、月に4回程度しか開催されないコンテストに10回出るには3か月近くかかってしまう。もっと少なくても大丈夫という情報は無いのか。ただし、アルゴリズムの勉強は最小限にしたい。
そんなことを思ったので、少し調べてみた。
結論
8回くらい参加すれば茶色になれるかも！
よって、2か月くらいで茶色になれる可能性はある。詳細は後述する。
この記事を書いた理由
AtCoder を知って参加したり勉強していたのだが、「本を買ってアルゴリズムを10個程度覚えて練習を頑張る必要がある」みたいな記事を見て「そんなには頑張りたくないな、、」と思ってしまった。
（言い訳だが、 アルゴリズムの勉強ではなくプログラミングをしたいと思ってしまうのだ。 特殊なアルゴリズムを覚えてもAtCoderで実際に活かせる機会も少なく、仕事で使う機会も少ない気が個人的にはしており、AtCoderの為だけに10個も20個もアルゴリズムを覚えるのは少し気が重い。）
また、元々は何も知らずに「緑色くらい行けるでしょ！」と思ってAtCoderをやってみたところ、思っていたより茶色になるまで時間がかかってしまいモチベにも影響しているため、情報を整理しておきたいと考えた。
そこで色々調べてみたところ、緑色以上になるにはアルゴリズムの勉強が割と必要な印象だが、茶色であれば必要ない気がした。そこで、まずはそこまでアルゴリズムの勉強をせず茶色になるにはどれくらいかかるかを調べたくなった。
ちなみに、10回程度必要だと言われている理由の1つは「9回までの初期補正」で、もう1つは下記の記事で紹介されている「ユーザの参加回数とレーティングの中央値」の情報かと思っています。
参考：1-6-5. コンテストに出まくる！ - レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 #競技プログラミング - Qiita
補足
念のためですが、AtCoder はコンテスト1回毎に結果は出て、それが何色相当かは分かります。なので、1,2回だけでも茶色くらいの結果が出るかどうかは分かります。今回この記事で書くのはあくまでアカウントに紐づくレーティングの話になります。
詳細（その1）
AtCoderには AtCoder Beginner Contest (通称ABC) という初心者向けのコンテストがある。まずはこれだけに参加する想定で、直近のコンテスト（2024年6月1日～2024年8月31日）を自分なりに分析し、どの程度の難易度を正解し、何回出れば良いかを考える。
また、必要な参加回数を推定するための判断材料とした「初期補正」と「パフォーマンス」について記載し、それによってどのように回数の推定を実施したかを書いていく。
ABCと問題の難易度について
ABCでは最近は基本的に7問の問題があり、難易度の低い順に問題A~Gまで存在している。
問題ABは初学者でも基本的には解ける可能性が高く、問題Cも場合によっては解けると聞く。
そう判断できる根拠の1つは AtCoder Problems というサイトだ。このサイトでは過去のAtCoderのコンテストの問題と概ねの難易度が確認できる。問題ABは基本灰色であり、問題Cは灰色か茶色か緑色だ。
上でも書いたが、緑色以上になるとアルゴリズムの知識が必要なケースは多い。
そのあたりの情報を元に 「汎用性の低いアルゴリズムなどは学ばずに、問題ABCを可能な範囲で解くことを仮定して、概ね何回のコンテストで茶色になれるか」 をこの記事では考える。
補足
コンテストの名称である AtCoder Beginner Contest の略称がABCなのだが、この記事では「問題A,問題B,問題C」のことを略して「問題ABC」と記載する。分かりにくくて申し訳ない。
また、筆者は理系なので数列などある程度の数学の知識はあるため、そのあたりの知識もない方の場合は少し印象が違うかもしれないし、もう少し参加回数が増えてしまう可能性はある。（解けない問題が増えてしまうかもしれないため）
初期補正
コンテストの出場回数が少ないうちはマイナスの補正がかかるようになっている。
AtCoderの実力は、たくさんのコンテストに参加しないと、正確に測ることが出来ません。ですので、参加回数の少ないうちは、レーティングを低く設定しています。
| AtCoderコンテストへの参加回数 | 表示メッセージ | 補正されているレーティング |
|---|---|---|
| 5回未満 | 推定される実力よりも大幅に低いレーティングとなっています。 | 400以上 |
| 9回未満 | 推定される実力よりも少し低いレーティングとなっています。 | 200以上 |
| 14回未満 | 推定される実力よりも若干低いレーティングとなっています。 | 100以上 |
この5回と9回という閾値は今回の推定では重要になる。
パフォーマンス
パフォーマンスとは、そのコンテストにおいてどの程度のレーティングと判定されたかを示す値である。高いほど実際のレーティングにも高く反映される。
今回は、アルゴリズムの勉強などはせず問題ABCの3問のみを回答する想定でどの程度のパフォーマンスになるかを確認する。
詳細は後述するが、直近のコンテストを確認したところ 問題ABCを全て回答すればパフォーマンスは 400~700 くらいになる。 これは、茶色程度のパフォーマンスである。
初期補正とパフォーマンスを考慮する
参加回数 5回未満
初期補正は 5回未満だと 400以上になる。これは非常に大きい。なぜなら、茶色になる最低ライン 400を目指すのに、初期補正が 400なのでその倍の 800程度のレーティングが必要になるという意味だからだ。レーティング 800と言うのは緑色の実力が必要と言うことだ。これは、問題ABCの3問だけを回答するのでは中々難しいと考えている。（上で書いたように、パフォーマンスが800以上を目指すには、問題ABCを回答する前提ではかなり難しいためだ）
（ちなみに、実力があれば 1,2回でも茶色にはなれる。その辺も少しはデータを見たり検討してみたので後述する）
参加回数 5~9回
5回コンテストに参加することで400以上の補正が200以上になる。そうなると、600程度のレーティングであれば茶色になり得る。 これは、問題ABCの3問だけを解くのでも達成しうる。
これを考慮すると 5回でも茶色になれそうと思ったのだが、パフォーマンス茶色の方で茶色になっている方を数百人くらいざっとデータを目視で見てみたりしたのだが、5~7回で茶色になっている人はほとんど見つけられなかった。5~7回で茶色になっている人は大抵パフォーマンスが緑色以上の結果を出していた。
おそらく 5回を超えた時点で過去分も含めて全成績が補正される訳ではないので、パフォーマンスが毎回600だとしても 5回では茶色にならないのだろうという気がする。8,9回くらいで茶色になっている方は見かけた気がするので、それくらいであれば可能性はある気がする。
とはいえ数は少ない。大抵茶色で安定せず緑色とか高めのパフォーマンスが出たり、灰色以下の低いパフォーマンスが出てしまうので、パフォーマンス600を8回だけ出した、みたいなケースが非常に少ないためだ。
そのため、目視で色々な人を見た印象としてもパフォーマンスが茶色の方は 10回以上で茶色になっているケースが多かった。やはり 10回くらいは想定しておくと良いのかもしれない。 今回の記事としては「絶対に10回必要という訳ではなく、8回くらいでもワンチャンあるよ！」ということを言いたい。
詳細（その2）
ある程度の情報は上記でまとめた通りだが、更なる詳細について後述する。気になる方だけ読めば良いと思います。
パフォーマンスの仕組み
先ほど「600程度のパフォーマンスが出れば良い」というような話をしたが、そもそもどういう計算で算出されるのかについて、自分が確認した範囲で記載すると下記の通りである。
- コンテストでの順位が高いとパフォーマンスは高くなる
- 順位は、正解した問題による得点が高い方が高い。得点が同じ場合はかかった時間が短い方が高い。
- 正解した問題のうち最も最後に正解した時刻が早いと高くなる
- ただし、正解した問題のうち間違った回答を提出した場合、その回数によるペナルティが加算される
- 1回の誤答提出につき5分追加される
- 正解した問題のうち最も最後に正解した時刻が早いと高くなる
例えば、問題ABCを正解した人(X,Y,Z)が3人いた時、かつそれより正解数の多い人が1111人いた場合、下記のようになる。
- 1112位 Xさん（30分10秒で正解、誤答なし）
- 1113位 Yさん（30分15秒で正解、誤答なし）
- 1114位 Zさん（20分40秒で正解、ただし2回誤答を提出した。よって+2×5分で30分40秒）
パフォーマンスの仕組みから考えるコンテスト参加時の注意点
上記のような仕組みのため、パフォーマンスを高くするためには誤答の提出は減らすべきである。そのため、簡単な問題でもちゃんとテストしてイージーミスは減らした方が良い。とは言え 1回5分なので慎重になり過ぎる必要はない。無駄な誤答は減らせるだけ減らせるようにすべき、というレベル。（良く分からないけれど正解にならないから、考えながらもう一回そのまま提出してみる、みたいなことは減らすべき）
各コンテストのパフォーマンス値や参考値
直近のコンテストの「順位表」などの情報を元に、問題ABCの3問を全て解いた場合、どの程度のパフォーマンスになるかを確認した。（ABC359のみ問題Cの難易度が高かったため、ABのみ回答するケースも参考値として記載した）
その値や参考値は下記の通り。
| コンテスト | パフォーマンス | 参加者数 | 順位 | 時間 |
|---|---|---|---|---|
| ABC369 | 400 ~ 687 | 9649 | 4924 ~ 6764 | 8:58 ~ 180:41 |
| ABC368 | 399* ~ 807 | 9786 | 4272 ~ 6772 | 8:49 ~ 159:39 |
| ABC367 | 346 ~ 993 | 10494 | 3313 ~ 7658 | 1:17 ~ 192:24 |
| ABC366 | 362 ~ 669* | 10670 | 5428 ~ 7581 | 7:49 ~ 169:22 |
| ABC365 | 350 ~ 758 | 11202 | 4985 ~ 7968 | 2:41 ~ 202:05 |
| ABC364 | 277 ~ 1081 | 10189 | 2695 ~ 7787 | 5:34 ~ 163:28 |
| ABC363 | 628 ~ 952 | 10518 | 3551 ~ 5804 | 3:38 ~ 135:31 |
| ABC362 | 471 ~ 688 | 10983 | 5418 ~ 6917 | 4:26 ~ 162:30 |
| ABC361 | 566 ~ 1017 | 10556 | 3212 ~ 6059 | 2:36 ~ 181:00 |
| ABC360 | 505* ~ 803 | 8513 | 3577 ~ 5198 | 7:14 ~ 182:52 |
| ABC359(AB) | 89 ~ 721 | 10644 | 4871 ~ 10306 | 1:05 ~ 229:07 |
| ABC359 | 724 ~ 1114 | 10644 | 2638 ~ 4809 | 12:06 ~ 182:55 |
| ABC358 | 325 ~ 494 | 11041 | 6652 ~ 7891 | 2:54 ~ 139:29 |
| ABC357 | 429 ~ 933 | 10999 | 3635 ~ 7034 | 2:14 ~ 163:35 |
| ABC356 | 620 ~ 917 | 11653 | 3940 ~ 6181 | 2:48 ~ 153:01 |
（*は、実際のトップはnoratedで参加しておりパフォーマンスがついていなかったため、その次の人でratedの参加者の値を記載している）
（参加者数は問題Aの提出数を参考値として記載している）
この情報を見ると分かるが、コンテストによっては問題ABCの3問全てを解ければいくら時間がかかっても600以上のパフォーマンスになるケースがある。これは、問題Cの難易度が高いケースだ。逆に、3問全てを解いても600未満のパフォーマンスになっているケースもある。これは問題Dの難易度が低いケースだ。
当たり前だがコンテストによって上記のようにパフォーマンスの上下はあり、それが多少の運要素ではある。とはいえ、基本的には3問解いて、その中でも割と上位のスピードで提出が出来ていれば600程度になるだろう。
補足
本来は中央値や平均値を算出して、上位何%とか、何分程度でとか、そういう情報まで出せれば良かったのだが面倒で諦めました。
また、最低値と最高値を表には記載してますが、どちらもかなり外れ値です。最低と最高なので当たり前ですが。あくまで「これだけ早く解いてもこの程度のパフォーマンスにしかならない」ということと、逆に「誤答の提出回数が多過ぎることでペナルティが付き過ぎてパフォーマンスが落ちるケースがある」ということの参考値として見てもらえたら良いと考えています。
（しょうがないことな気はしますが、時間の最大値はどれもペナルティによるものなので、ペナルティによってパフォーマンスが低めに出てしまう人はペナルティを減らすことを少し意識するだけでも改善しそうな気がします。）
初期補正について
400以下のパフォーマンスが出てしまうと更に補正がかかるようです。そのため、ただ参加回数を稼ぐために参加登録をするのはおそらく逆効果です。また、例えば初めて参加した時に色々勝手が分からず 0問正解！みたいなことになると、茶色を目指すのに必要な参加回数が増えてしまう可能性はある気がしてます。
なお、AtCoderのレーティングにおいては、400未満のレーティングはさらに補正をかけておりますので、コンテストに出続けることで、補正されたレーティングがそのまま上がることを保証するわけではありません。
とはいえ、10回実施すれば初期補正は更に下がるし、下記に記載されている「参加回数」と「レーティングの中央値」の表にあるように、10回参加のレーティング中央値は 521 のため 10回参加で茶色になれる可能性は割と高いはずであり、意図的に「回数を稼ぐために参加登録して、問題は解かない」みたいなことをしない限りはそれほど気にしなくて良いとは思います。
参考：1-6-5. コンテストに出まくる！ - レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 #競技プログラミング - Qiita
低いパフォーマンスはちゃんと影響する
調査している中で、パフォーマンスが水色や緑色を出したことがあるのに茶色になっていない方を何人か見たのですが、共通点は「かなり低いパフォーマンスのコンテスト結果が散見される」ことでした。
その低いパフォーマンスの詳細を見ると、「1問も回答せず低パフォーマンスになっているもの」でした。そのため、参加したらちゃんと毎回頑張りましょう。また、当たり前ですが参加できないコンテストには参加登録しないようにしましょう。
（昔より最近はそういう参加者が増えたこともあって、レーティングが多少上がりやすくなっている、みたいなことはあるかもしれないです。全然調べてないので分からないですが。）
補足
ARC に参加する場合
約月1回開催されるAtCoder Regular Contest(ARC)があります。中級者以上向けという噂ですが、茶色を目指す人が参加するのは良いのか悪いのか。これも検討しましたが、参加しない方が良い印象はあります。
まず、問題の難易度が高いです。ABCの問題Cと問題Dの間くらいの印象です。
過去問を1,2問解いてみて、行けそうならチャレンジしても良いですが、上にも書いたように「低いパフォーマンスはちゃんと影響する」ため、参加して1問も解けなかった場合は100~300くらいのパフォーマンスになってしまい、茶色を最短で目指す場合は逆効果、または影響なしになる気がしています。
次のコンテストでどれくらいのパフォーマンスを出せば良いか
「あと何回くらい？」というのは分からないが、「次の1回のコンテストでどれくらいのパフォーマンスを出せば茶色になれるか」みたいなことは下記のサイトを使えば推定できます。
問題ABだけで茶色になれるか
下記で検討されていましたので、そちらを参考してください。
※順位の数値について
どうでもよい話だが、コンテストの「順位表」の「順位表」での順位と「レーティング変動」での順位がズレているケースがある。詳細は不明だが、アカウントが削除された場合に「順位表」は削除前の情報で表示されており、「レーティング変動」の方の順位の記載は削除後の値に更新されていることによって発生しているように見える。今回、「各コンテストのパフォーマンス値や参考値」で表に記載したのは「順位表」に表示される値です。
実力が高い場合
そもそも実力が高い場合は1,2回で茶色になれます。そのあたりも少し確認したため記載しておきます。
1回のコンテストで茶色になれる人
直近のコンテストを見る限りでは 青色以上のパフォーマンス(1600以上)が出る場合は1回で茶色になります。
ちなみに、初回補正は青色以上の場合は -1200のようです。そのため、茶色の最低値400になるには、1回目で 400 + 1200 = 1600 以上が必要になる、という計算です。
コンテストで青色以上のパフォーマンス(1600以上)を出すには
どれくらいのレベルかと言うと、コンテストで上位10%(最近だと1000位以内)くらいが青色パフォーマンスになる気がします。（直近のコンテストの「順位表」の「レーティング変動」でレーティングと順位の関係を見た印象）
どれくらい問題を解ける必要があるかというと、コンテストによりますが問題ABCDEFG の 7問のうち FGの2問以外を全て回答し、その中でも時間が早いくらいのレベル以上の必要がありそうです。 （コンテストによっては5問正解で時間は真ん中くらいでも上位10%になることはあるようです。）
2回のコンテストで茶色になれる人
基本的には2回のうち1回でも青色以上なら茶色になりそうです。 (あまりそういう方がいなかったので分からないですが。)
また、 水色2回なら概ね茶色になりそうです。
水色+緑色の2回で茶色になっている方もいました。水色+茶色もありました。ただ、なっていない方もいたためパフォーマンスの数値次第の様です。
ちなみに、緑色2回では茶色には届かないようです。
コンテストで水色以上のパフォーマンス(1200以上)を出すには
どれくらいのレベルかと言うと、コンテストで上位20%(最近だと2000位以内)くらいが水色パフォーマンスになる印象です。
どれくらい問題を解ける必要があるかと言うと、コンテストによりますが 基本的には問題ABCD の4問を全て回答し、その中でも時間が短い方になる必要がありそうです。
さらに、コンテストによっては問題Eまでの5問を回答しないと届かない場合があったり、CやDが難しい場合に、ABEの3問を回答していないと届かないケースはあります。何にせよ、問題ABCD 4問以上を解けるような実力が必要です。
2回以降の初期補正値
1回目は補正値の計算が分かりやすいんですが、2回目以降は良く分からないので詳細は確認していません。
3回のコンテストで茶色になれる人
この辺からはあまり情報として意味がない気がしますが、概ね 緑色以上で3連続の場合は茶色になる印象です。
どれくらい、という表現がどんどん難しくなってくるので詳細は記載しません。
おわりに
個人的に色々気になっていたことを確認して整理できたので良かったです。気が向いたら次は「二分探索と動的計画法(DP)だけ勉強したら緑色になれるか」なども検討してみたいですね。
ちなみに、自分は 12回くらいで茶色になれました。うち、2回は ARCで 0問正解でしたし、ABCでも 0問や 1問だけ正解を 2回くらいやらかしました。やっぱ 10回くらいかかるのね、、とこんな記事を書いておいて残念な気持ちにはなりました。3か月くらいかかっちゃいましたしｗ とは言え、ミスらなければ 8回くらいで行けてた気もするので記事で書いたことはそれほどズレてはいないんじゃなかろうかと思ってます。
最短で目指す上で自分がやらかしたミスや所感など、そういうのは機会があれば別の記事で書こうかなとは思ってます。
個人的には AtCoder のハードルが少し高いとは思っていて、「最低10回は参加しなきゃいけない」とか「アルゴリズムを色々勉強しなきゃいけない」みたいなハードルを少しでも下げられたら良いなと思ったので、そんな風に誰かに影響を与えられたら嬉しい限りです。その他まあ何でも少しでも参考になれば幸いです！
何か間違いがあればコメント頂けると助かります。