SupershipでVPoEをしている名畑です。2023年冬アニメのテクノロイド オーバーマインドを見ていて、その内容からうたプリを思い出していたら、上松範康さんの作品だと後から知りました。ストーリー展開が予想外で面白いです。
AtCoderについて調べてみたシリーズの過去記事
はじめに
競技プログラミングのサイトであるAtCoderには下記3種類の代表的なコンテストがあります(Heuristic Contestというものもありますが今回の記事では対象外とします)。
- AtCoder Beginner Contest(通称ABC)
- AtCoder Regular Contest(通称ARC)
- AtCoder Grand Contest(通称AGC)
ABC、ARC、AGCの順番に対象ユーザのレベルが上がり、問題の難易度も上がります。
また、AtCoderではコンテストの順位が大きくは下記の3つで決まります。
- どれだけの問題を解いたか(正答数で得点が決まる。問題毎に得点は異なる)
- どれだけの速さで解いたか(同一得点のときは解いた時間で決まる)
- どれだけミスをせずに解いたか(ミス数に応じて時間が加算される)
(絶対ではないですが)同一コンテストではA問題、B問題、C問題……と段階的に難易度が上がっていきます。つまり、A問題が最も簡単です。
たとえば初心者向けであろうABCのA問題は、大体の場合、プログラミングの基本的な文法知識(ifなど)があれば手こずらない難易度です。
ARCのA問題やAGCのA問題になると、競技プログラミングの経験がまったくないと厳しいでしょう。
こういった各コンテストのA問題をユーザはどれぐらいの時間で解くのか、そしてレーティング(色)によって速度にどれだけ違いがあるのか、今回は集計してみました。
AtCoderをやっていると自分より上の色のユーザは手の届かない化け物に見えるものですが、実際にどれだけ遠い存在なのか、あるいは近い存在なのかの可視化を試みての一環です。色と実力の関連の数値化とも言えますね。
結論としては「暖色ユーザってやっぱりえげつないし、寒色ユーザもえげつない」と思いました。
前提
前提がそれなりに長いです。
いきなり結果を見たい方はこちらをクリックしてください。
問題を解く流れ
AtCoderをやったことがない人のために、問題を解く流れを簡単に記載しておきます。
- 問題を開く
- 問題を読む
- コードを書く
- 入力例を試す
- コードを提出する
提出したコードが正しければいいので、入力例を試さない人はいるのかもしれません。
色について
AtCoderの色はそのユーザが上位何%にいるかを示します。
色 | レーティング |
---|---|
赤 | 上位0.3% |
橙 | 上位1% |
黄 | 上位3% |
青 | 上位7% |
水 | 上位15% |
緑 | 上位30% |
茶 | 上位50% |
灰 | 1回でも参加 |
赤〜黄を暖色コーダと呼ぶらしいです。青と水は寒色コーダですかね?
AtCoderの社長である高橋様のブログ記事を読むと色毎の実力がより把握できると思います。「赤はもうなんか世界大会とかに招待されたりする」だそうです。
調査対象の問題
- ABC 285(2023/1/15開催)
- ABC 284(2023/1/7開催)
- ARC 153(2023/1/14開催)
- ARC 152(2022/11/20開催)
- AGC 060(2022/12/25開催)
- AGC 059(2022/12/4開催)
上記6コンテストそれぞれのA問題を対象とします。
A問題だけに絞った主な理由は集計のしやすさです。
調査対象ユーザ
各コンテストにおけるレーティング変更対象のユーザのみを対象としています。つまりは評価を懸けて挑んでいる人たちということです。
- ABCの場合は青まで
- ARCの場合は橙まで
- AGCの場合は水以上
- その上でコンテストにおいてRatedにしている
※AtCoderではUnrated(レート反映対象外)にして参加することもできます。
解答時間(解答速度)の定義
まず、解答時間を求める上での対象となる提出を下記とします。
- 対象ユーザのコンテスト時間内でのA問題でのACであること
- 対象ユーザのコンテスト時間内での最初のACであること
- 対象ユーザのコンテスト時間内での最初の提出がA問題であること
つまり「最初の提出がA問題でWA」「2度目の提出もA問題でAC」であれば「2度目の提出が対象」となります。
「最初の提出がB問題でWA」「2度目の提出がA問題でAC」の場合は対象にはしていません。
対象となる提出を求めた上で提出時間とコンテスト開始時間の差を解答時間としています。
「最初に全問題を読んだ上でA問題から解き始める」という人もいるかもしれませんが、その場合は「全問題を読んだ時間も解答時間に含まれる」となります。
※ ACは正答のこと、WAは誤答のこと
算出した値
平均値と中央値と最上位色倍率をコンテストと色別に算出しました。
最上位色倍率はそのコンテストにおける最上位色(ABCなら青、ARCなら橙、AGCなら赤)と比較して中央値が何倍かです。
値がばらつく上に最大値がほぼコンテスト時間一杯(ABCなら6,000秒、ARCなら7,200秒、AGCなら10,800秒)となりうるため、平均値より中央値の方が比較には適していそうです。1人でもコンテスト時間をA問題ですべて使った人がいたなら、平均をかなり押し上げてしまうため。
結果
ここから先が結果となります。
コンテスト毎にまとめています。
ABC 285 A問題 Edge Checker 2
- コンテスト名:AtCoder Beginner Contest 285
- コンテスト時間:2023-01-15(日) 21:00 ~ 2023-01-15(日) 22:40 (100分)
- A問題:Edge Checker 2
木を知ってさえいれば非常にシンプルな問題です。たとえ知らなくても点の数が15個と固定されているので解答まで難なくたどり着けるでしょう。
私が試しに書いたACコードは下記(Python(3.8.2))です。これぐらいのコードを書くことが求められる問題なのだとイメージするのにお役立てください。
A, B = map(int, input().split())
if A == B // 2:
print("Yes")
else:
print("No")
集計結果は以下の通りです。
色 | ユーザ数(人) | 平均値(秒) | 中央値(秒) | 最上位色倍率 |
---|---|---|---|---|
青 | 233 | 90.16 | 72 | 1.00 |
水 | 500 | 132.35 | 94.5 | 1.31 |
緑 | 841 | 157.46 | 117 | 1.63 |
茶 | 1095 | 253.13 | 165 | 2.29 |
灰 | 2387 | 641.79 | 367 | 5.10 |
無 | 432 | 850.46 | 549.5 | 7.63 |
計 | 5488 | 436.61 | 210 | 2.92 |
無はunratedです。つまり初挑戦。
最終行には参考までに色別に分けていない数値を計として記載しておきました。
1問でもACしたユーザ数は5,666人で、最初の提出並びにACがA問題であるユーザ数は5,488人でした。大半のユーザはA問題から解き始めるのですね。
こうやって見ると色毎にはっきり差が出るものだと感じます。
中央値で比較した場合、青ユーザは1分強でコード提出までを済ませていますが、灰ユーザだと6分強かかっている。
ある程度競技プログラミングに慣れているであろう茶色以上のユーザであれば見た瞬間に正答が思い浮かびそうな難易度の問題ですが、それでも、茶と青の間に2.29という倍以上の速度差があります。本当にどこでここまで差が出てるんですかと言いたくなってしまう。
問題読んで解答書いて提出までに1分って冷静に考えて高速すぎて、青コーダの時点ですごすぎます。
ちなみに、最小値は表には載せていませんが青〜緑はすべて20秒台(20秒〜29秒)でした。AtCoderはコンテスト参加回数を重ねないとレーティングが低めに出ることがあるため、どの色にも現在の色以上の実力の持ち主はいるのでしょう。
それにしても20秒って……。
ABC 284 A問題 Sequence of Strings
- コンテスト名:AtCoder Beginner Contest 284
- コンテスト時間:2023-01-07(土) 21:00 ~ 2023-01-07(土) 22:40 (100分)
- A問題:Sequence of Strings
入力を逆順で出力していくだけです。
試しに書いたACコードは下記(Python(3.8.2))です。
N = int(input())
S = [""] * N
for i in range(N):
S[N - i - 1] = input()
[print(i) for i in S]
集計結果は下記の通りです。
色 | ユーザ数(人) | 平均値(秒) | 中央値(秒) | 最上位色倍率 |
---|---|---|---|---|
青 | 358 | 98.85 | 65 | 1.00 |
水 | 602 | 107.35 | 77 | 1.18 |
緑 | 1012 | 130.38 | 92 | 1.42 |
茶 | 1352 | 167.30 | 112 | 1.72 |
灰 | 2536 | 439.23 | 216 | 3.32 |
無 | 870 | 592.75 | 299 | 4.60 |
計 | 6730 | 310.21 | 138 | 2.12 |
ABC 285より全体的に時間は短くなっていますが、ハイレーティングな人ほど速く解く傾向は共通です。
ARC 153 A問題 AABCDDEFE
- コンテスト名:AtCoder Regular Contest 153
- コンテスト時間:2023-01-14(土) 21:00 ~ 2023-01-14(土) 23:00 (120分)
- A問題:AABCDDEFE
試しに書いたACコードは下記(Python(3.8.2))です。コメントは不要です(私が振り返る際のために書きました)。
# S2とS6とS9は他が決まれば一意に決まる
# S1S3S4S5S7S8を6桁の整数とすると100000から999999である
N = int(input())
s = str(N + 99999) # Nが1のとき100000
print(s[0] + s[0] + s[1] + s[2] + s[3] + s[3] + s[4] + s[5] + s[4])
集計結果は下記の通りです。
色 | ユーザ数(人) | 平均値(秒) | 中央値(秒) | 最上位色倍率 |
---|---|---|---|---|
橙 | 68 | 278.01 | 237.5 | 1.00 |
黄 | 220 | 335.15 | 285 | 1.20 |
青 | 281 | 509.15 | 391 | 1.65 |
水 | 414 | 616.23 | 513.5 | 2.16 |
緑 | 520 | 921.94 | 709 | 2.99 |
茶 | 507 | 1387.86 | 1072 | 4.51 |
灰 | 853 | 2179.88 | 1757 | 7.40 |
無 | 229 | 1951.55 | 1547 | 6.51 |
計 | 3092 | 1287.27 | 802 | 3.38 |
中央値を見ると2つ上の色がおおよそ1.5倍〜2倍の速度ですかね。
青と比較して橙は1.65倍、水と比較して黄は1.80倍、緑と比較して青は1.81倍、茶と比較して水は2.08倍。
暖色コーダである橙や黄の人は5分もかけていない。化け物すぎます。
これ、コードだけ見るとシンプルに見えますが、緑の私なんかだと、コンテスト中という時間に制限がある中だとなかなか即座に「6桁の整数として考えられること」「文字列を使うと処理しやすいこと」が思いつかないんですよね。
AtCoderでは「速く書けて速く動くアルゴリズムをいかにして速く頭の引き出しから取り出すか」が求められるのですが、それが本当に難しい。
無が灰より速いというのがABCとは異なる傾向ですが、初めての挑戦でARCを選ぶような方たちなので、かなりの実力者が混ざっているってことですかね。
ARC 152 A問題 Seat Occupation
- コンテスト名:AtCoder Regular Contest 152
- コンテスト時間:2022-11-20(日) 21:00 ~ 2022-11-20(日) 23:00 (120分)
- A問題:Seat Occupation
試しに書いたACコードは下記(Python(3.8.2))です。これももちろんコメントは不要です。
# 1席空けで座っていって端まで行った状態で2人組が来たなら座れない
N, L = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for val in a:
count += val
if count > L and val == 2:
print("No")
exit()
count += 1 # 1席空ける
print("Yes")
集計結果は下記の通りです。
色 | ユーザ数(人) | 平均値(秒) | 中央値(秒) | 最上位色倍率 |
---|---|---|---|---|
橙 | 49 | 387.69 | 298 | 1.00 |
黄 | 203 | 469.89 | 383 | 1.29 |
青 | 252 | 607.60 | 512.5 | 1.72 |
水 | 298 | 910.30 | 736 | 2.47 |
緑 | 342 | 1208.69 | 996 | 3.34 |
茶 | 230 | 1942.94 | 1487 | 4.99 |
灰 | 249 | 2570.02 | 2063 | 6.92 |
無 | 59 | 1846.69 | 1284 | 4.31 |
計 | 1682 | 1277.00 | 818 | 2.74 |
この問題も2つ上の色がおおよそ1.5倍〜2倍の速度というのは同様ですかね。青と比較して橙は1.72倍、黄と比較して水は1.91倍、緑と比較して青は1.94倍、茶と比較して水は2.02倍。
無が灰より速いという傾向もARC 153同様です。
AGC 060 A問題 No Majority
- コンテスト名:AtCoder Grand Contest 060
- コンテスト時間:2022-12-25(日) 21:00 ~ 2022-12-26(月) 00:00 (180分)
- A問題:No Majority
お試しコードはなしで。実際にユーザたちが提出したコードはこちらで見ることができますが、ご自身で解いてみていただいても楽しいかと(化け物度合いを感じてみてほしい)。
集計結果は下記の通りです。
色 | ユーザ数(人) | 平均値(秒) | 中央値(秒) | 最上位色倍率 |
---|---|---|---|---|
赤 | 50 | 418.52 | 351 | 1.00 |
橙 | 73 | 578.96 | 443 | 1.26 |
黄 | 194 | 798.46 | 628.5 | 1.79 |
青 | 183 | 1478.88 | 1134 | 3.23 |
水 | 180 | 2983.92 | 2426.5 | 6.91 |
計 | 680 | 1508.58 | 860.5 | 2.45 |
赤は橙をさらに上回る速度なのだと示されました。赤は橙の1.26倍の速度、黄の1.79倍の速度、青の3.23倍の速度。青でも私からすれば化け物なのに。
AGC 059 A問題 My Last ABC Problem
- コンテスト名:AtCoder Grand Contest 059
- コンテスト時間:2022-12-04(日) 21:00 ~ 2022-12-05(月) 00:00 (180分)
- A問題:My Last ABC Problem
本問題もお試しコードはなしで。ユーザが提出したコードはこちらです。
集計結果は下記の通りです。
色 | ユーザ数(人) | 平均値(秒) | 中央値(秒) | 最上位色倍率 |
---|---|---|---|---|
赤 | 39 | 1506.59 | 1104 | 1.00 |
橙 | 39 | 2480.79 | 1997 | 1.81 |
黄 | 74 | 3121.01 | 2716.5 | 2.46 |
青 | 51 | 3762.75 | 3300 | 2.99 |
水 | 19 | 4941.21 | 4732 | 4.29 |
計 | 222 | 3028.14 | 2453 | 2.22 |
こちらも色が上がるほどに中央値は小さくなっていきます。上には上がいるというのを痛感させられる結果です。
ちなみに、この回はA問題の難易度が高かったからか、B問題の正答者数の方がA問題の正答者数よりも多かったです。
最後に
高橋様のこの投稿を実感する結果でした。
【競プロの各色に対する認識オススメ】
— chokudai(高橋 直大)🐙🔥@AtCoder社長 (@chokudai) June 29, 2020
・2色上は人外だと思うのが大切!比較しちゃだめ!1色上に追いついたところで人間に戻してあげよう!
・1色上は強い人!目標にするのは良いけど勝てなくて当たり前!いつかは追いつけたらいいなくらいに思おう!
・同色でも成長がヤバいやつはやっぱり人外!
宣伝
SupershipのQiita Organizationを合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。
Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方はSupership株式会社 採用サイトよりご確認ください。