chokudaiのブログ

chokudai(高橋直大)のブログです

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

近頃「AtCoderの色を就活等でアピールしたい時に上手く出来ない!」と言われるので、「どれくらいのレベルの人なの?」という説明と、エンジニアさん向けに「実際どういう問題が解けるの?」というまとめを書いておきたいと思います。解き方のヒントが書いちゃってあるので、自分で解きたい人は、ヒントを読む前に解いてください。

 

 

大前提:AtCoderについて

AtCoderは、プログラミングのコンテストを開催している企業です。「もの作りのアイデアを競う」だとか、「製品を作る」という部分から少し乖離した、「複雑な処理を正しく記述する」だったり、「計算時間のかかる処理を、数学的/情報科学的にスマートに処理する」だったりを競うコンテストになります。多くの人が参加できるようにするため、専門分野に対する知識等は出題されず、ベースとなるアルゴリズムに関する問題が出題されます。コンテストは毎週開催され、3000人ほどが同時に参加しております。

採点は完全に機械的に行われ、想定通りの答えが出力されていれば正解となります。人間の好みに左右されることがない、確かな評価となります。

 

このようなコンテストであるため、エンジニアに必要な、全ての能力が測定できるわけではありません。必要な項目は、以下の資料(AtCoderの営業資料の一部)をご確認ください。

f:id:chokudai:20190131162210p:plain

AtCoderJobsでの参加者の説明

 

AtCoderの色・ランクと、その実力

さて、AtCoderのコンテストに参加すると、コンテスト成績に応じてレーティングが変化します。これによって、AtCoder上における、レートの色が変化します。

下の画像は自分のレーティングの変化です。

f:id:chokudai:20190131163759p:plain

AtCoderのユーザーページ(chokudai)

これは僕のレーティンググラフなので異常に高いんですが、400ごとに色がついていて、赤・橙・黄・青・水・緑・茶・灰・黒、という順番になってます。

誤解を恐れずに超ざっくりとイメージでの評価をするなら、

  • 灰色は参加すれば誰でもなれるので意欲以外の保証はなし。
  • 学生で茶色なら優秀だがエンジニアとしてはちょっと物足りない。派遣とかで来たエンジニアが茶色あれば一安心。
  • 緑あれば大抵の企業でアルゴリズム力は十分。AtCoder的には決して上位ではないが、他社評価サイトなら最高評価。
  • 水色だと基礎的なアルゴリズム処理能力については疑いのないレベル。
  • 青以上は一部上場のIT企業でも、一人もいないことが結構あるレベルになる。
  • 黄色からは化け物。競プロの問題を解く機械だと思っておけば良い。
  • 橙はあたまおかしい。
  • 赤はもうなんか世界大会とかに招待されたりする。

って感じに思っておけばいいです。誤解をしたくない人は、以下に詳しい説明があります。

 

灰色 (Eランク Rating ~399)

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

AtCoderのコンテストが足りなくてレーティングが上がりきってない、って人はごめんなさい><)

 

茶色 (Dランク Rating 400~799 上位50%)

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

個人的な印象としては、

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

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

  • 標準入出力、if、forなどの単純な操作はできる
  • 問題文を正しく理解し、仕様通りの実装をすることが出来る
  • 複雑な問題や、数学的処理が必要な問題を解決する能力はない

という印象です。コーディング試験でおなじみFizzBuzzは簡単に組める水準です。

茶色の人の半数が解ける問題と時間を並べます。

 

B - Polygon 要求タイム:5分

整数の配列を受け取り、配列が条件を満たすか(Max, Sumが絡んだ計算式。計算方法自体は問題文に記述あり)を求める問題です。

C - Grand Garden 要求タイム:80分

素数Nの0埋めされた配列が初期状態として与えられ、区間を指定してその区間の要素を1増やす操作が出来るときに、与えられた整数列を作るために必要な最小手数を求める問題です。

多少の考察を要求する問題です。いわゆる「数学」や「アルゴリズム」というレベルの問題ではなく、「やりたいことを実現するにはどういう手順を踏めば良いか」を考えるタイプの問題です。(僕自身は、こういう部分が「アルゴリズム」の本質的な部分であり、○○法みたいなものよりよっぽど大切だと思っていますが。)

 

緑色 (Cランク R800~1199 上位30%)

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

印象としては、

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

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

技術的な部分では、

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

という感じです。

 

緑色の人の半数が解ける問題と時間を並べます。

C - ID 1時間

データが与えられるので、グループごとに順序を整理し、ID番号を生成する問題です。素直な実装力を求められる問題はAtCoderでは多くないですが、普通に書くと30行くらいの機能を実装する能力があることが分かります。

C - Streamline 20分

簡単な一人ゲームが与えられるので、最小手数を求める問題です。どちらかというとAtCoderのこのランクの問題は、こうした基本的な論理的思考力の方が求められることが多いです。

 

水色 (Bランク R1200~1599 上位15%)

水色はかなり優秀です。普通に企業とかで超優秀って言ってるプログラマが居た時に、半分くらいはこのランクになると思います。数学が得意なタイプだと、この一つの上の青色に行きますが。

半数以上のIT企業において、アルゴリズム能力についてはカンストと言えるでしょう。特にアルゴリズム的な能力を必要としない会社であれば、ここから上はレートを上げても実務に役立つ部分はほとんどありません。

技術的なスキルで言うと、

  • 計算量に関する感覚が体に染みついており、複雑な処理でも苦もなく実装出来る
  • 深さ優先探索幅優先探索、順列の全列挙やパターンの全列挙などができる。そこから動的計画法やメモ化再帰などの計算量改善につなげることも多少出来る。
  • 貪欲・DP・しゃくとり法・二分探索などの計算量を改善するテクニックをある程度使い分けることが出来る。
  • 累積和やUnionFind(競プロ外ではDisjoint Set)などのデータ構造を使いこなすことが出来る。
  • ダイクストラ法やワーシャルフロイド法、クラスカル法などの、基本的なグラフアルゴリズムが扱える。木構造やグラフ構造に対して適切に処理を行うことが出来る。
  • 一定以上の数学に関する素養がある。素数などの性質や、それを利用した素数判定や列挙、約数の列挙等、最小公倍数や最大公約数、組み合わせの計算など、競プロにありがちな典型数学問題に対処できる。

みたいな感じになります。水色になると急に要求水準が上がってるのは分かると思います。

水色の人の半数が解ける問題と時間を並べます。

D - Xor Sum 2 60分

数列が与えられるので、XorとSumが一致する区間の数を求める問題です。Xorなどのbit演算の基礎知識が与えられた上で、効率的に処理するデータ構造とアルゴリズムを考える必要があります。このあたりから、アルゴリズムの勉強をしたことがない人には手が付けられない問題になってきます。

 

D - AtCoder Express 2 60分

最初に区間がN個が与えられ、その後Q個の区間クエリが与えられるので、完全に内包している区間がどれだけあるかを求める問題です。入力される値が小さいので、例えばWavelet Treeなどの複雑なデータ構造を用いなくても解くことができますが、区間を二次元上にマッピングする発想を出すこと自体が少し難しいです。

 

青色 (Aランク R1600~1999 上位7%)

 青は超優秀です。学生時代を競技プログラミングに注ぎ込んでも、ここにたどり着けない学生は大量にいます。競技プログラミング未経験者では、このレベルと競技プログラミングで戦うことは殆どの場合は無理です。8割以上のIT企業において、アルゴリズム力はカンストです。一部企業においては、少し持て余してしまうかもしれません。

技術的な要素は以下の通りです。

  • 複雑な処理でも難なく高速に実装出来る。
  • 水色のアルゴリズム知識に加え、最大流やSegment Treeなど、高度なアルゴリズム、の知識がある。
  • データ構造やアルゴリズムを知っているだけでなく、適切な場面で活用することが出来る。
  • どういう問題の時にどういう計算量改善の方法があるか、というような、典型テクニックを多く知っている。
  • 複雑な計算量改善を要求された際に、紙などを用いてきちんと考察を進めることが出来る
  • その他、水色で書いたことのレベルが一段階上昇している

って感じでしょうか?水色や青あたりで、競技プログラミングで必要な知識はほぼ揃ってしまうので、そこから先は応用力の違いになってきてしまいます。

青色の人の半数が解ける問題と時間を並べます。

 

C - Alternating Path 20分 (1時間だと水色)

グリッドグラフが与えられるので、白黒の頂点を交互に辿ってたどり着ける頂点のペアの個数を求める問題です。基本的な幅優先探索が出来るのはもちろん、そこからペアの数を纏めて数えるための考察などが必要になります。時間を掛ければ解ける問題ではありますが、この考察を短時間で解けるのがこのランクの強みです。

 

D - Equal Cut 60分

数列を切り分ける問題です。(数列が多く出題されていますが、データ構造やアルゴリズム等をシンプルに問うのに、数列は非常に便利です)

4つの区間の和の最大値と最小値の差が出来るだけ小さくなるように区間を切り分ける問題です。こちらも一筋縄で解ける問題ではありませんが、特別なアルゴリズムの知識は全く必要なく解けるAtCoderらしい問題です。深い考察力が要求されます。

 

黄色 (Sランク R2000~2399 上位3%)

九割以上のIT企業において、このレベルのアルゴリズム構築能力は必要ありません。研究職・研究開発などや、高度なアルゴリズムを要求される開発現場で重宝されます。 

といいつつ、普通にプログラマとして役立つので来て欲しい、みたいな発信はSoundHoundさんとかがしてたりするので、エンジニアとして役立つ場面も多々あるのかな、と思ってます。「うちでは役立つ!」って言ってる企業さんもたくさんあるので。

能力的には、数学的な思考力、論理的な思考力、アルゴリズムに関する知識、正確で高速な実装力に関して、大幅なアドバンテージがあります。別にエンジニアリング力は全然保証してませんが、賢い人が多いので統計を取ったら高い可能性はあるかもしれません。このランクになると、新卒採用においてはポテンシャル採用という意味でめちゃくちゃ評価されている印象です。

 黄色の人の半数が解ける問題と時間を並べます。

 

D - Nearest Card Game 60分

二人ゲームで、カードを取る順序が与えられるので、先攻プレイヤーが取るカードの和を答える問題です。愚直に計算すると当然間に合わないので、上手く処理を高速化してあげる必要があります。処理の高速化自体のアルゴリズムは、非常に難しいというわけではないですが、境界の処理とかがかなり面倒で、見た目以上に実装に苦労するタイプの問題です。

 

D - Median of Medians 60分

数列が与えられるので、その数列で考えられるすべての区間に対する中央値を列挙し、その値の中央値を求める問題です。かなり数学的な問題ですが、アプローチ自体はかなり情報科学的な定跡を用いて解いていくタイプの問題です。大抵の人にはとっかかりすらつかめない難問です。

 

橙色 (SSランク R2400~2799 上位1%)

ここまで来ると、検索サービスとかの滅茶苦茶アルゴリズムが大切な会社さんとか、研究開発とか、そういうところじゃないとこのアルゴリズム力は生かせない気がします。

といいつつ、普通のエンジニアの新卒採用でもかなり優遇されています。やっぱりポテンシャル採用なのかなあと思っています。ただやっぱりこのランクの能力めっちゃ生かせる!って言ってる企業もちょこちょこあります。

橙色の人の半数が解ける問題と時間を並べます。

 

E - Weights on Vertices and Edges 60分

グラフに関する問題です。まず基本的な貪欲法でO(N^2)まではすぐ見えるかと思います。(水色くらいの水準) ここからいかに計算量を落とすかの問題です。例えば永続UnionFindやDynamic Connectivityなど、連結成分を管理する難しめのデータ構造が見えますが、考えをきちんと整理すると、計算順序を上手く整理すればUnion-Findなどの簡単なデータ構造だけで比較的簡単に書くことができます。

 

D - Reversed LCS 40分

文字列Sが与えられる。このSをK文字まで変更した文字列をTとして、Tと、Reverse(T)の最長共通部分列の長さを最大化する問題です。そもそも最長共通部分列の知識があるものとして、まずこの最長共通部分列がどのような特徴を持つかを考察するパートをこなした上で、適切な動的計画法の式に落とし込めるかどうかが問われる難問です。

 

赤色 (SSSランク R2800~3199 上位0.3%)

この辺から化け物しかいないので説明をサボります。僕もここです。

問題

E - Wandering TKHS 80分

木構造が与えられた時に色々する問題です。難しいです。

銀王冠 (SSSランク R3200~3599 上位0.1%)

頭おかしいです。ここに行きたいです。最早意味もない気がするので問題も貼りません。

金王冠 (SSSランク R3600~ 上位0.03%)

化け物です。そもそも日本に一人しかいないです。世界でも九人しかいません。

 

 

 

 おおよそのレベル帯が分かりましたでしょうか?何かこれも書いておくべき!みたいなのがあればコメントやブクマ等で書いてもらえるとありがたいです!