先日のAtCoder Beginner Contest 424でようやく入緑することができた。足掛け3年。長い道のりだった。言語はPython*1。
とりあえず祝ってほしいので先に干し芋を貼っておく。記事執筆時点であと2人で読者が100人になるので、お祝いに読者になってくれるとめちゃくちゃ嬉しい。
アルゴリズム部門での緑色以上の人数割合は レーティングのしくみ - AtCoderInfo によると2023 年時点で 7.86 % 程度。全体だと15.48%に入るらしい。
色ごとの絶対的な実力はchokudaiさんのエントリによるとこんな感じ。
印象としては、
- 学生ならかなり優秀。
- エンジニアとしてもある程度の安心感がある。論理的に複雑な処理の実装に対応できない、なんてことはなさそう、くらいには思える。データ量が多い現場など、計算量の多い処理が要求される現場でなければ、このレート帯以上を求める必要はほぼない。
くらいの印象です。もちろんアルゴリズム力しか計ってないので個人差があります。
技術的な部分では、
- if、forはもちろん、それを組み合わせて2次元配列に対して操作をしたり、深さ優先探索や幅優先探索などのキューや再帰を使った実装も出来る。
- 簡単な動的計画法の問題や、数学的に工夫する問題など、計算量の工夫も出来始める。
という感じです。
緑コーダーになったことで、プログラマとして基本的人権を得た安心感がある。
以降は自分語り。
モチベーション
2022年ごろに転職を決意したのが最初のモチベーション。コーディングテストの練習のためにAtCoderをやり始めた。が、全然解けない...。これはイカンということで半年ほど基礎からみっちりやった。茶色に到達したタイミングで転職活動を始めるとともに、灰色に戻りたくないという思いからしばらく放置。
しかし最近になって「UoPとかでCSを取りたい」「いつか外資で働いてみたい」と思うように。そのために「もう少し数学やアルゴリズムの基礎力を上げたいな」と考えはじめた。
そして以下の動画で「GAFAのコーディング試験はAtCoderでいうと緑くらいのレベル」と話しているのを聞き、再びAtCoderと向き合うことを決意。入緑をモチベーションにしてここまでやってきた*2。
今後
引退する。緑になれた時点で目的を達成し、モチベーションを失ったから。
数学やアルゴリズムの基礎力という点では、chokudaiさんの緑コーダーへの印象通りの力がついたと思う。ちなみに水色だと、
水色はかなり優秀です。普通に企業とかで超優秀って言ってるプログラマが居た時に、半分くらいはこのランクになると思います。数学が得意なタイプだと、この一つの上の青色に行きますが。
半数以上のIT企業において、アルゴリズム能力についてはカンストと言えるでしょう。特にアルゴリズム的な能力を必要としない会社であれば、ここから上はレートを上げても実務に役立つ部分はほとんどありません。
技術的なスキルで言うと、
- 計算量に関する感覚が体に染みついており、複雑な処理でも苦もなく実装出来る
- 深さ優先探索や幅優先探索、順列の全列挙やパターンの全列挙などができる。そこから動的計画法やメモ化再帰などの計算量改善につなげることも多少出来る。
- 貪欲・DP・しゃくとり法・二分探索などの計算量を改善するテクニックをある程度使い分けることが出来る。
- 累積和やUnionFind(競プロ外ではDisjoint Set)などのデータ構造を使いこなすことが出来る。
- ダイクストラ法やワーシャルフロイド法、クラスカル法などの、基本的なグラフアルゴリズムが扱える。木構造やグラフ構造に対して適切に処理を行うことが出来る。
- 一定以上の数学に関する素養がある。素数などの性質や、それを利用した素数判定や列挙、約数の列挙等、最小公倍数や最大公約数、組み合わせの計算など、競プロにありがちな典型数学問題に対処できる。
なんだけど、この辺も普通にできないと今は緑になれないんじゃね？と思う。
以下は仮説だが...
2019/02/11に書かれたchokudaiさんのエントリだと水色は上位15%となっている。一方でレーティングのしくみ - AtCoderInfo を見ると今の緑コーダーも大体上位15%くらいに入る。なので今のAtCoder環境は、2019年に書かれたchokudaiさんのエントリ基準だと1つずつくらい印象がずれるんじゃないかと*3。今はもう色で能力は測れなくて、"上位n%に入るにはこれができないと"って見方をする方がいいのではないかと思っている。
その辺の細かい話はさておき...ここから先上位10%前半の集団の世界は、数学が好きだったり得意な人が進む道なんだと思っている。自分は、数学はほどほどに好きで、全然得意でもない*4。だから、もうここで十分満足だ。少なくともAIがどんなアルゴリズムを書いてきても、ちゃんと理解してレビューするには十分なアルゴリズム基礎力がついたと思う。
緑になるまでやったこと
基本的には自分の力不足と馬鹿さ加減に滅入る気持ちと闘い、山のふもとで小さな歩みを始めることが大事。
数学を基礎からやりなおした
naoyaさんの入水エントリでもおすすめされているとおり、数学入門からやり直した。
遠山啓先生の著書は読者に「数学って面白いな」と思わせながら、それでいて数学の基礎がわかるように書かれているのでとてもおすすめ。数学入門以外にも何冊か読んだ。
本の解説を読んで練習問題をやったり、無料コンテンツをやったり
緑くらいまでを目標にするなら、個人的に最初の一冊は佐野さんの本がおすすめ。
その後は典型90問を一通り解いた。
自分はDPが苦手なので、けんちょんさんの解説を読みながら忘れた頃にEducational DPを繰り返しやった。ちなみに今もDPは苦手。
その次に鉄則本を通しでやった。
1日1ACもやったけど苦痛だし続かないので最近はコンテストにだけ出てた
当初は1日1ACをやっていた。けど、数学がそこまで好きではないのでモチベーションが続かない... それにAtCoderを勉強のメインに据えるわけにはいかなかった。途中でReactやKotlinのキャッチアップをしないといけなくなったり...と仕事で必要な技術のキャッチアップが定期的に発生する。もちろん優先度は仕事の方が高い。そのうえ勉強していて楽しいのは後者だった。そうすると1日1ACは全然続かない。
なので途中からは1日1AC方式をやめた。代わりに毎週末のABCの終了後にAtCoder Problemsでまとめて解く。そして、解けた問題の次の問題までを解説などをみて学習するようにした*5。で、苦手な分野がわかってきたら、今度はコンテストをお休みしてAtCoderの問題を分類しましたシリーズでその分野ばかりやるようにする。これをやるようになってから、「あーこれはたぶんこのアルゴリズムだな」とあたりがつく確率が高くなった。
おしまい
AtCoderのおかげで数学とアルゴリズムの基礎力に自信を持てた。次はAtCoderに割いてた時間を英語に注力していくぞぉぉぉ。
あとはフェルミ推定をもっと練習したい。AtCoderの問題は基本的に「既知の解法をどう使うか？」っていう問題が多いけど、今度は解法を自分自身で作る訓練を積んでいきたい。
まあ優秀な新卒たちはどちらも大学生のうちに使いこなせるようになってるんだろうけどね... と嘆いても現状は変わらない。今が人生で一番若いので引き続き精進する。
以上。最後は大好きなサークライさんで締めます。
*1:Pythonである理由は特にない。AtCoderではスタンダードのC++でないのは、実務で使うことがないから。C++の次に解説コードが多く、実務で使うこともあったのがPythonだったから。というくらいの理由。おかげでPythonがスラスラ書けるようにはなったので、結果としてPython選んでよかったと思う。
*2:leetcodeは知ってるけどやってない。やりかけのAtCoderを緑にしたい気持ちの方が強かった。
*3:実際、けんちょんさんもAtCoder界隈のインフレ具合を感じてそう。https://x.com/drken1215/status/1959830980640010546
*4:なので緑になるまでいっぱい練習した
*5:例えばB問題まで解けてC問題が全くわからんかったらC問題だけ復習する。D問題から先は放置、といった感じ
