AtCoderの色(灰~緑)とレベルの関係について

AtCoder の色とレベルの関係(灰~緑)について、思うことを書いていきます。

この記事は、かなり主観が入っています。より客観的な色とレベルの関係が知りたい方は、AtCoder コンテストについての tips という記事が参考になると思います。

目次

用語解説

ABC

AtCoder Beginner Contest のこと。初心者~中級者向けのコンテスト。

レーティング 2000 未満(青色まで)の人が Rated(レート変動あり)になる。

以前、ABC が 4 問体制だった頃はレーティング 1200 未満(緑色まで)が Rated だった。その頃の ABC は初心者向けのコンテストだったが、今の ABC(6 問体制)は中級者も対象になっている。

特に E,F 問題は中級者向けの問題(初心者には手が出ないことが多い)なので、はじめのうちは E,F 問題が解けなくても大丈夫。

AGC

AtCoder Grand Contest のこと。上級者向けのコンテスト。

Rated の制限がなく、全員がレート変動の対象となる。

正直、難易度の傾斜が激しすぎて初心者にはおすすめできない。が、レートが低いうちは AGC の A 問題を速く解くことでレートが大きく上がることもあるので、時間があるなら参加しても良いだろう。

ただ、ABC と AGC では、配点が同じでも難易度は段違いなので、解けなくても落ち込む必要はない。

ところで、AGC の「まだまだプログラミングを始めたばかりという人も、一度参加されてみてはいかがでしょうか?」という文言はネタなんですか?正気とは思えないんですが。

レーティング

AtCoder に参加している人の「強さ」を表す数値。高ければ高いほど、難しい問題も解くことができるということを表す。

パフォーマンス

AtCoder の各回のコンテスト(ABC,AGC など)における成績を表す数値。この数値が高いほど、その回のコンテストで優秀な成績を収めたことを表す。

Difficulty

AtCoder の問題(1 問)の難易度を表す数値。AtCoder Problems というサイトで確認することができる。

「コンテスト時間内にその問題を解ける可能性が 50%のレーティング」を表していて、「Difficulty1200」なら、「レーティング 1200 の人なら 50%解ける問題」ということになる。(おそらく)非公式の値だが、体感の難易度と一致していると思う。

ただし、ABC041 以前の ABC(通称「旧旧 ABC」)の Difficulty は、最近の問題の Difficulty と比べて大きくずれているので注意。体感よりも半色~一色半(200 ~ 600)前後 Difficulty が高く出ているように感じる。

旧旧 ABC に限らず、少し古い問題の Difficulty は今よりも高く出ている事が多いと思う。(それだけ多くの人が難しい問題を解けるようになっているのだろう)

2020/03/14 追記:AtCoder Problems で、旧旧 ABC の難易度推定が改善され、体感とのズレが小さくなりました。

AtCoder では、レーティングごとに「色」を振り分け、その人の強さがわかりやすいようにしている(他のコンテストサイトでも同じような概念はある)。

AtCoder では、以下のようになっている。

範囲
[0, 400)
[400, 800)
[800, 1200)
[1200, 1600)
[1600, 2000)
[2000, 2400)
[2400, 2800)
2800 以上

そして、AtCoder 界隈の人はレーティングだけでなく、パフォーマンスや Difficulty も「色」で呼ぶ習性がある。

  • パフォーマンス 1000:緑パフォーマンス(緑パフォ、緑 Perf)
  • Difficulty1500:水 Difficulty(水 Diff)

AtCoder の色とレベルについて

AtCoder の色(ここでの「色」はレーティングのこと)とレベルの関係については、AtCoder 社の社長である高橋直大(Chokudai)氏が 2019 年 2 月に書いた記事があります。公式の見解が知りたい方は AtCoder(競技プログラミング)の色・ランクと実力評価、問題例をご覧ください。

しかし、この記事は微妙に古いです。2019 年 2 月当時は、約 3000 人が ABC に参加していたようですが、2020 年 1 月時点では約 6000 人、2020 年 4 月現在では約 10000 人が参加しています。

また、競プロに入門するための資料も充実してきており、参加者のレベルがかなり上がっています。

そのためなのか、記事に書かれている色とレベルの関係は、体感とは微妙にずれているように感じます。(私自身が水色なので、青色以上のことはわかりませんが)

ここからは、私の体感の色とレベルの関係を書いていきたいと思います。

灰色(Rating 0-399)

灰色になる条件は、AtCoder に 1 回参加する、です。ということなので、AtCoder が保証できる実力は全くありません。灰色な人はもうちょっとたくさんコンテストで出たり、実力を上げたりして頑張ってください……><

AtCoder(競技プログラミング)の色・ランクと実力評価、問題例

これは、あくまでも「『AtCoder で灰色である』という肩書が保証できる最低限の実力」ということに注意する必要があります。

実際に ABC に 1 回参加し、(間違っていたとしても)回答を提出するだけで灰色になることができます。(回答を 1 回も提出しないと、不参加扱いされて灰色になれません。ご注意ください)

しかし、AtCoder で灰色ならば全然実力がないとは限りません。

AtCoder には、参加回数が少ないとレーティングが低く出る傾向があります(リセマラ防止の為らしい)。この傾向は、参加回数が 10 回に満たないときに顕著です。

そのため、数回参加した程度ではレートが上がりきっていない可能性が高いです。

ですから、参加回数が 10 回未満の方は、レーティングが灰色だからといって落ち込む必要はありません。繰り返し参加して、より高いレートを目指しましょう。

ここからは、10 回以上参加している場合の色とレベルの関係を、各色上位と下位に分けて見ていきます。

灰色下位(Rating 0-199)

10 回以上参加してレーティングが灰色下位の方は、プログラミングの基礎が身についていない可能性があります。

具体的には、

  • if
  • for
  • 数値と文字列
  • 変数
  • 配列
  • 標準入出力

といったものです。

これらは、プログラミングをしていく上で欠かせない知識ですので、ぜひ勉強しましょう。

ただし、標準入出力は、競プロ特有の知識が必要かもしれません。

  • 1 つだけの入力
  • スペース区切りの入力
  • はじめに与えられる入力の行数が渡されて、その行数だけ受け取る入力

など、様々なパターンがあるので、わからないものがあれば「◯◯(言語名) 競プロ 入出力」のように検索しましょう。ある程度メジャーな言語であれば、誰かが解説記事を上げてくれている事が多いです。

※AtCoder では、コンテスト中の検索は許可されています。わからないことがあったら、気軽に検索しましょう。

ただし、コンテスト中、SNS 等に「順位表から読み取れる情報(例:50 分で全完した など)」以外の情報を漏らすのは厳禁です。「B 問題は ◯◯ で解ける」「C 問題が難しかった」などの発言は、コンテスト終了後にしましょう。

灰色上位に行くには、(回によって難易度が異なるので一概には言えませんが)A,B 問題をできるだけ速く(15 ~ 20 分程度)解く必要があるでしょう。C 問題が簡単な回もあるので、時間があったら C 問題にも挑戦すると良いと思います。

灰色上位(Rating 200-399)

Chokudai 氏のブログには「AtCoder が保証できる実力は全くありません」とありましたが、Rating200 以上になれるのであれば、プログラミングの基本的な文法(if,for など)は身についていると思います。

学生であれば、このレベルでもある程度の実力はあると思います。FizzBuzz も簡単に組めるでしょうし、2 重ループや 3 重ループも問題なく書けるでしょう。

ただ、エンジニアであれば少し物足りないかもしれません。

ここから茶色を目指すには、

  • C 易 D 易回:A,B,C 問題をある程度速く(30 ~ 40 分程度)解き、D 問題も解く
  • C 易 D 難回:A,B,C 問題をある程度速く(30 ~ 40 分程度)解く
  • C 難 D 難回:A,B 問題を速解き(10 分前後)し、C 問題を頑張る

のいずれかをする必要があります(時間はあくまでも目安です)。これは、正直かなりレベルが高いです。

ここから先は、過去問を解く(通称:精進する)必要があるかもしれません。精進の際には、AtCoder Problems を活用することをおすすめします。

このサイトで、Difficulty が灰色と茶色の問題を解いていくと良いでしょう。

また、

  • コンテスト後の解説 PDF を読む
  • コンテスト後の解説放送(Youtube)を見る
  • Qiita やブログなどの解説記事を見る
  • 競プロ er の解説放送・解説動画を見る

といったことも効果的です。特に公式の解説放送はわかりやすくておすすめです。

解説 PDF・解説放送を見てもわからない場合は、「ABC◯◯ C 問題」のように検索し、その問題を解説している記事を読むと良いでしょう。

また、わからない用語が登場したときは、「競プロ ◯◯」のように検索すると良いです。競プロ関連の知識をわかりやすくまとめてくださっている方も多いので、積極的に調べると良いと思います。

Twitter などで「C 問題は簡単だ」みたいな発言を目にしたとしても、気にする必要はありません。C 問題は、決して簡単ではないと思います。

確かに簡単な回もあるのですが、C 問題を安定して解こうとすると、どうしても競プロへの慣れが必要になります。

競プロが強い人達は競プロをやりすぎて感覚が麻痺しているだけなので、強い人が「エンジニアなら C 問題を解くのは当たり前」のような事を言っていたとしても、自信をなくす必要はありません。(もちろん、その煽り文句で精進のやる気が出るなら良いのですが)

茶色(Rating 400-799)

茶色になる条件は、Rating が 400 以上になることです。茶色で保証できる実力ですが、正直あまり高いレベルではありません。ただ、ここにたどり着く前に辞めてしまい人が多いので、十分にやる気がある人であるとは言えるでしょう。

個人的な印象としては、

  • 情報系の学生が茶色であれば、ちゃんと勉強してるなって印象になる
  • 派遣で来たプログラマが AtCoder 茶色だったら結構安心する
  • 茶色があればエンジニアとしてアルゴリズム面においての安心感があるかと言われたら、正直物足りない

みたいな印象があります。スキル的には、

  • 標準入出力、if、for などの単純な操作はできる
  • 問題文を正しく理解し、仕様通りの実装をすることが出来る
  • 複雑な問題や、数学的処理が必要な問題を解決する能力はない という印象です。コーディング試験でおなじみ FizzBuzz は簡単に組める水準です。

AtCoder(競技プログラミング)の色・ランクと実力評価、問題例

正直、今の茶色は「あまり高いレベルではありません」なんて言えません。

解説放送や解説記事などの充実により、茶色を維持するために必要な知識がかなり増えています。そのため、

  • 学生で茶色なら優秀
  • エンジニアで茶色なら十分

くらいだと思います。

茶色下位(Rating 400-599)

学生であれば、茶色下位でも優秀です。エンジニアでも茶色下位で十分だと思います。

さて、ここから茶色上位を目指すには、

  • C 易 D 易回:A,B,C 問題速解き(20 分以内)、D 問題も解く
  • C 易 D 難回:A,B,C 問題速解き(20 分以内)、D 問題を頑張る
  • C 難 D 難回:A,B 問題を速解き(10 分以内)、C 問題も解く

くらいが必要です。

C 問題以降は、精進なしでは普通に難しいと思います。一部数学の知識があれば簡単なものもありますが、多くの問題は慣れないと解けません。

ここから先は精進量が物を言う世界になるので、時間に余裕がない場合はここで競プロをやめても良いでしょう。ここまで来られる方であればある程度のコーディング力はあると思いますし、貴重な時間を削って無理やりコンテストに出る必要はありません。

ある程度精進する時間を取れるという方や、競プロを楽しいと感じている方は、茶色上位~緑色下位を目指すと良いと思います。

精進する時には、解いていて 10 ~ 20 分くらい方針が浮かばなかったらすぐに解説を見ることをおすすめします。というのも、この段階で解けない問題というのは、知識不足であることが多いからです。

知識不足で解けない問題についてずっと悩んでいるのも馬鹿らしいので、はじめのうちはすぐに解説を見るようにすると良いでしょう。

茶色上位を目指すにあたって覚えておきたい知識
  • 累積和:かなり重要な知識です。真っ先に覚えましょう。
  • 簡単な二分探索/二分法:慣れるまでは普通に難しいです。めぐる式二分探索がバグらせにくいのでおすすめです。
  • next_permutation:たまに出てきます。知っていると役に立つかもしれません。
  • GCD(最大公約数)/LCM(最小公倍数):ユークリッドの互除法を使います。実装方法は調べるとたくさん出てきます。
  • 素数判定・素因数分解:エラトステネスの篩を使います。実装は調べれば出てくるはずです。
  • 時間計算量:オーダーってやつです。
    • 1 重ループなら$O(N)$
    • 2 重ループなら$O(N^2)$
    • 二分探索は$O(\log{N})$
    • ソートは$O(N\log{N})$
    • カッコの中が$10^9$くらいになると TLE(実行時間制限超過)する
    • 以上を知っていれば十分な気がします

これくらいです。比較的少ないですが、こんなことが要求されるのにレベルが高くないわけがないだろ!

補足

AtCoder のジャッジシステムは、実行時間制限+100ms で強制的にプログラムが止まり、TLE 判定になります。

「時間制限が 2000ms で実行時間が 2103ms だから、もう少しだけコードを改善すれば AC になる!」と TLE になるコードを大量に投げるのはやめましょう。ジャッジシステムが詰まって他人の迷惑になります。

茶色上位(Rating 600-799)

学生ならとても優秀、エンジニアでも優秀です。

このレベルに精進なしで到達できるのは一部のエリートだけです。凡人は精進で目指します。

ここから緑色下位を目指すには、基本的に 4 完が必要です。D が簡単なら速解きも必要です。

そして、D 問題を安定して解くためには、業務ではあまり使わない(と思う)競プロ特有の知識が必須になります(next_permutation も使わないと思うけど)。

緑色を目指すにあたって覚えておきたい知識
  • imos 法(いもす法):累積和とセットで覚えるとお得です。怖そうな名前をしていますが、考え方はシンプルです。慣れましょう。
  • 簡単な BFS(幅優先探索)/DFS(深さ優先探索):知識としては知っていても、実装できなければ意味がありません。慣れましょう。
  • 簡単な DP(動的計画法):はじめはさっぱりわかりませんでした。慣れればできるようになるのですが、慣れるまでがかなり大変です。慣れましょう。
  • bit 全探索:集合を全探索する書き方があります。はじめは意味不明かもしれませんが、慣れれば書けるようになります。慣れましょう。
  • UnionFind:たまに出てきます。慣れましょう。
  • priority_queue:たまに出てきます。正直、競プロをやるまで存在を知りませんでした。慣れましょう。
  • 計算量の見積もり
    • $N = 10^9$ だと $O(N)$ は間に合わないが $O(1)$ や $O(\log{N})$ なら通る
    • $N = 10^5$ だと $O(N^2)$ は間に合わないが $O(N)$ や $O(N\log{N})$ なら通る
    • $N = 10^3$ だと $O(N^3)$ は間に合わないが $O(N^2)$ や $O(N^2\log{N})$ なら通る
    • $N = 30$ だと $O(2^N)$ が間に合わない
    • みたいな感じです。慣れると簡単です。慣れましょう。

検索すると解説記事がたくさん出てくるので、その記事を読むか、「蟻本(プログラミングコンテストチャレンジブック 第 2 版 [ISBN978-4-8399-4106-2])」と呼ばれる競プロ界のバイブルを買って読みましょう。

そもそも、こんな知識が要求されるのは緑~水くらいだったんじゃないんですか?正直、茶~緑にこれを要求するのはかなりやばいと思います。

緑色(Rating 800-1199)

緑色になれれば、「競技プログラミングに熱心に取り組んでいる人」と考えて問題ないでしょう。要求レベルも決して低くなく、出場回数が足りないとマイナス補正がかかるため、運だけで到達することはまず出来ないラインです。他社アルゴリズム力判定サービスだと、上位1%の最高ランクが付く実力です。(あくまで「アルゴリズム力部分だけであることに注意してください)

印象としては、

  • 学生ならかなり優秀。
  • エンジニアとしてもある程度の安心感がある。論理的に複雑な処理の実装に対応できない、なんてことはなさそう、くらいには思える

くらいの印象です。もちろんアルゴリズム力しか計ってないので個人差があります。

技術的な部分では、

  • if、for はもちろん、それを組み合わせて 2 次元配列に対して操作をしたり、深さ優先探索や幅優先探索などのキューや再帰を使った実装も出来る。
  • 簡単な動的計画法の問題や、少し数学的に工夫する問題など、計算量の工夫も出来始める。 という感じです。

AtCoder(競技プログラミング)の色・ランクと実力評価、問題例

学生でもエンジニアでも、このレベルに到達できたのならとても優秀です。そして、ここから先は趣味の領域になります。

「プログラミング技術を向上させたい」といった目的で競プロをやっているのなら、他のことをしたほうがよっぽど有益です。

薄々気づいているかもしれませんが、ここからは「どれだけ精進したか」でレートが決まります。しかも、一部の天才が一瞬で水色や青色になっていくのを横目に見ながら精進をしなければなりません。

競プロが楽しくなければやめましょう。楽しくないと続きません。

緑色下位(Rating 800-999)

  • 組み合わせ・順列($_n\mathrm{C}_k$ , $_n\mathrm{P}_k$)
  • 確率・期待値
  • 逆元
  • XOR(排他的論理和)

といった数学的な知識が問われるようになってきます。その他にも、様々な数学的センスが問われます。

凡人は精進を重ねて慣れるしかありません。このような数学的な問題の解説は蟻本に載っていますし、解説記事も充実しています。

茶色上位で紹介した事項をしっかり身につけ、こうした数学の知識を身につけることができれば、緑色上位に行けると思います。

緑色上位に行くには、ABC で 4 完速解きが必要です。精進しましょう。

また、4 完速解きをするために、ライブラリを用意しておくことが必要になるかもしれません。とっさにコードが書けないアルゴリズムや、いつも実装方法を調べてしまう処理などは、ライブラリとして整備しておくと楽です。

緑色上位(Rating 1000-1199)

水色になるには、E をある程度解けるようにする必要があります。これは、もう精進あるのみです。

E を解くのに必要な知識は(多分)全部蟻本に書かれているので、読みましょう(初級編から中級編まで、ざっと読めば十分です)。そして、精進しましょう。

E を解くためには、ある程度の考察力が必要です。過去問を解く際は、すぐに解説を読まずに、30 分くらいは考えたほうが良いかもしれません(このあたりは好みだと思いますが)。

偉そうに言っていますが、私自身は蟻本をあまり読んでいません。わからない問題が出てきたら蟻本に載っていないか調べる、位でも十分な気はします。

まとめ

後半がすごい適当になってしまいましたが、言いたいのは

  • 最近灰~緑のレベルが上がっている気がする
  • 灰色とか茶色とかでも落ち込む必要はないよ

ということです。

この記事で書いた各色のレベル感/各色になるために覚えておきたいことなどは、あくまでも私の体感です。AtCoder のレートは相対的なものであるため、これらは少しずつ変化すると思われます(もちろん、個人の能力にも大きく依存します)。ご注意ください。

追記

AtCoder の色到達難易度は本当に上がったか? ~レーティング分布の変化の真相を探る~

こんな PDF が上がっていました。

  • 正答率はほぼ変化していないが、(緑~水色周辺の)パフォーマンス・Difficulty が出にくくなっている
  • この傾向は 2019 年前半から終わりにかけて徐々に大きくなっている
  • その上がり幅は半色分(レーティング 200 前後)

といった部分は自分の体感に近く、(自分にとっては)かなり説得力のある内容になっています。

興味深い考察がされているので、ぜひ一度ご覧になってみてください。

Avatar
fiore

自称C++er。

comments powered by Disqus