Atcoder入緑したのでまとめ ~競技プログラミングは個人的には役に立ってる~

ざっくり内容

• 文系卒だけど Atcoder でなんとか緑になれた。
• 緑になるまでにやったこと、やらなかったこと。
• 競技プログラミングは結構役に立ってる
• とはいえ他にも大事なことはいっぱいあるよね

はじめに

こんにちは。k_xor_yama というアカウントで競プロやっているものです。

競技プログラミングサービス Atcoder で入緑できたので今までの軌跡をまとめたいと思います。

記事を書いてる人のスペック

• 1994 年生まれの 28 歳。最近東京から地元福岡に U ターン転職をキメてウキウキしている。でも東京がちょっと恋しい💔
• バックエンドエンジニア 3 年生。大学卒業後いったん別業種に就職したため、年齢のわりに歴は浅め
• 大学は外国語学部だったため、コンピュータサイエンスのバックグラウンドは 0 (Atcoder に参加してる大学生、高校生がまぶしい....)

緑の位置づけ

AtCoder（競技プログラミング）の色・ランクと実力評価、問題例から引用します。

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

• 学生ならかなり優秀。
• エンジニアとしてもある程度の安心感がある。論理的に複雑な処理の実装に対応できない、なんてことはなさそう、くらいには思える。データ量が多い現場など、計算量の多い処理が要求される現場でなければ、このレート帯以上を求める必要はほぼない。
  くらいの印象です。もちろんアルゴリズム力しか計ってないので個人差があります。
  技術的な部分では
• if、for はもちろん、それを組み合わせて 2 次元配列に対して操作をしたり、深さ優先探索や幅優先探索などのキューや再帰を使った実装も出来る。
• 簡単な動的計画法の問題や、数学的に工夫する問題など、計算量の工夫も出来始める。

この記事は 2019 年に書かれたものです。
最近は書籍やアルゴ式といった学習コンテンツが充実してきたこともあり、茶色~緑あたりは競争が激化しているとよく言われている気がします。 (私の周りだけだったらすいません)
かく言う昔のコンテストを知らない自分も、難易度の上昇感は感じています。(古い時代の緑 Diff のほうが大体簡単に解ける。)
特に一時期よくでていた UnionFind は昔なら緑 Diff がついたりしますが、最近は茶 Diff のイメージがありますね...

---

とはいえ、自分のレベルは上の記事に書いてある通り。またはそれ以下
(「よし複雑な処理をかけたぞ!! 🥳🥳」と思ってテスト書いてみると考慮漏れがあったりするので論理的に複雑な処理の実装に対応できていると胸をはっては言えない...)

なので、個人的には上の緑の実力評価は自分に関して言えば過大評価しっくりきます。

余談ですが、もう一つデータとして参加回数とレート平均、中央値を調べたので以下に示します。(2023 年 4 月現在)

参加回数	中央値	平均
5	107	262
10	254	451
20	542	679
30	741	875
40	800	890
50	868	945
100	1248	1398

30 回コンテストに参加したコンテスタントのレート平均が 875 であり、更に 40,50 回と参加回数を重ねても
中央値や平均値は 900 周辺なので、一口に「緑」といっても、800 周辺の人と四桁レートの間には結構大きな溝がありそうですね....!

TODO: 分散とかも調べてもう少しcoolな解析がここにのる

緑になるまでやったこと、やらなかったこと

やったこと

あまり特別なことはやっていません。

灰色時代からやったことを順番にまとめます。

佐野さんの「AtCoder 　凡人が『緑』になるための精選 50 問詳細解説」を解く

最初に手をつけました。優先度付きキューや約数列挙等が丁寧な解説付きでまとまっており、
1 冊目として取り組んで正解だったと思います。もし過去の自分にアドバイスするとしても、
この本からやるように勧めると思います。

https://algo-method.com/
今始めるならアルゴ式でもよいかなと思いましたが、

• ぱっと見で分量が多くて圧倒される
• 本当に始めたての人は「今の自分に足りない知識のコンテンツを選択する」ことができない

かな?と思ったので、おすすめです。

解説も図入りで丁寧に書かれており、こんなに手間のかかった本を低価格で提供してもらえるのは頭が上らないですね...!

Atcoder Problems で Recommendationをひたすら解く。

皆さんやってらっしゃると思います。割愛

典型 90 の星 4 以下を埋める

2 と並行して取り組み始めましたが、もうちょっと後か最初は星 2,3 まででよかったなと今では思います。

EDPC を途中まで頑張る(I まで解いた)

茶色に入ってから始めました。D 問題に動的計画法が出ることが多いので、動的計画法のお気持ちを理解しておくのは大事だと思います。(まだ難しい DP さんのお気持ちは理解できていない😵😵)

やらなかったこと

私の競技プログラミングをやる一番大きなモチベーションは、(レートをあげることも勿論ありますが)「業務に役に立つ形で知識を身につける」でした。

なので、「このアルゴリズムは緑を目指すには必要ない」といったことは考えずに、見聞きして興味がわいたデータ構造やアルゴリズムは試しました。

具体的には、

• treapを自分で書いてみる(いくつかのメソッドは未だバグらせ中...なんとか今月中には終わらせたい)
• Rustの標準ライブラリのBTreeMapやB木亜種のBε木の実装のお気持ちを読んでみる
• メモリに乗らない大量のデータセットに対しての様々なデータ構造を見てみる(Quotient FilterやCount Min Sketch等...)

などなど...

緑にはなるのに(というより下2つはatcoderのレートを上げるのに)必要ない(実際作ったImplicit treapは一度もコンテスト中につかわなかった)と思いますが、やはり実務と関連した知識というのは個人的にとてもテンションが上がるので、
適宜寄り道して楽しみながら学習しました。

競技プログラミングは役に立つか

よく「競技プログラミングは実務に役に立たない!」みたいな意見を聞きます。

役に立つ立たないの二元論で片付くほど単純なジャンルではないのかな。と思いますが、どちらかを選ぶなら「役に立つ」と思います

特に私のような文系卒でCSについて学んでこなかった人については高い確率で役に立つと思います。

根拠をいくつかあげます。

アルゴリズムを学ぶ = 仕事での問題解決能力向上につながる

競技プログラミングをやっていると、新しいデータ構造やアルゴリズムにたくさん出会いますよね。
(嬉しい半面頭を使う作業も沢山あるので大変!)

そういったものを深く学ぶことは、そのアルゴリズムがなぜ生まれたのか。といった背景についても学ぶということでもあり、業務で同じような問題に出会ったときに解法を類推することができるようになります。(私は全然そのレベルに達するほど知識の整理整頓ができていないのは秘密)

Rabin-karp法(ローリングハッシュ)を盗用検出ロジックの一部で使っているMOSSや、同様にAtcoderでよく見かける動的計画法(を使うWagner-Fischer法)を用いているfzfのスコアリング部分など、実際にAtcoderでよく使うアルゴリズムを用いているプロダクトについて色々と語って、「ほら！そこそこ役に立ちませんか！」と結論付けたいのですが、私の今のレベルだとゴミ低レベルな要領の悪い説明しかできない自信があるので、

以前拝見して「こんなに色々業務でも役に立つ知識があるんだな」と感動したkenkoooさんのestieでの記事へのリンクを置かせてください 🙌🙌

https://www.estie.jp/blog/entry/2022/08/04/113000

グラフ関連の用語に詳しくなれる

Atcoder ではグラフ問題がよく出てくるので、問題を解いてる内に自然と様々なグラフ関連の用語に触れることができます。

「グラフの知識なんてそんなに使わなくね...?」と思う方もいらっしゃると思いますが、
意外と...特に有向グラフはタスク間の依存関係を示すためによく用いられており、
日々の業務で触れる機会が今まで結構ありました。

Argo-Workflow

設定ファイルにDAG(有向非循環グラフ)^[1]という項目が出てきます。
大学でグラフ理論等をやっている場合は特に面食らうこともないと思いますが、全く前提知識がない状態で急に DAG という単語に出会ってもすぐに理解することは難しいと思います。

Ridgepole

Ruby on Rails を採用している会社だとよく見かける gem です。
この gem の version 0.8.3^[2] 以前にはトポロジカルソートをしているところでバグがあったようです。

DAG と同様、トポロジカルソートという用語自体を知らない場合どういうバグか想像するのは難しいと思います。
また、もしこのバグがまだ直ってなかったとして、Atcoderでトポソをよく書いていてデバックし慣れていれば、もしかしたら第一発見者としてコントリビュートできたかも...!

InQL

GraphQLのSchemaの循環参照を検出するツールです。(元々はBurpのExtentionですが、単体でもちゃんと動きます。)
Schema定義をTarjanのアルゴリズム ^[3]というアルゴリズムを使い、強連結成分分解して循環参照を検出します^[4]。
AtcoderをやってるとTarjanのアルゴリズムは知らなくても、SCC(強連結成分分解)は耳にしたことがあるのではないでしょうか。
わたしは本番でscc書ける自信はまだありません

未知の未知を知るきっかけになる / 普段使っている道具への理解が深まる

この項目はあんまり競技プログラミング自体とは関係なく、学ぶきっかけが競技プログラミングだった。という趣旨なので迷いましたが、せっかくなので残しときます。

無謀にもTreapを書いてみたと先に述べました。
とはいえなかなか難しく、実装につまると都度Rust標準ライブラリのBTreeMapがどのような実装になっているのかを見に行ったりしていました。

それまでお恥ずかしい話、「なぜMySQLのIndex TreeにはB+木が使われているのか」について
自分の言葉で説明できるほどの理解をしていなかったのですが、BTreeMapの実装を読み込んだり関連資料を漁ったりしている内に
「Binary Treeと比べてメモリの局所性がいいのと、N個のデータを検索するのにI/O回数が$\log_b N$(bはB木のブロックのサイズ)で済むから」
というようにちゃんと理解できました。

更にデータベースについての知識を見直す過程で、BigQueryのHyperLogLog関数やRedisで使われているBloom Filter,分散データベースで使われているConsistent Hashingといった馴染みの無かった大容量データに対してのデータ構造/アルゴリズムについても知ることができました。

---

また、お恥ずかしい話part2ですが(お前は恥ずかしい部分いっぱいの人間だな)、競技プログラミングにしっかりと取り組むまで、ハッシュテーブルの深い理解をしていませんでした。

競技プログラミングをやっている内に「C++のmapは赤黒木での実装なので各種操作が$\log N$らしい。(順番を保たなくてよいならunordered_mapなるものを使う)」ということを知り、
じゃあ他の言語のHashテーブルの内部実装ってどうなってるんだ?と興味が湧き、色々な資料をあさり始めました。

• ハッシュの衝突回避戦略は大きく分けてChaining(最悪計算量の上界:
  $O(\frac{\log n}{\log \log n})$^[5])とLinear Probing(最悪計算量: O($\log n$))があるのか。じゃあChainingの方が計算量的にはいい衝突回避戦略なのかな..?
• メモリの局所性をかんがえるとLinear Probingの方が一般的には性能がいいのか...今までこういった理論を知らずにHashテーブルを使っていたとは(唖然)...

といった感じにHashテーブルの実装についてしっかり学習することができました。
競プロをやってなかった場合Hashテーブルの実装についてちゃんとした理解が無いままずっと何食わぬ顔で業務をしていた可能性があり、本当にお恥ずかしい限りです...(懺悔)

とはいえ他にも大切なことは沢山あるよね

とここまで競技プログラミングやってきて良かったことをつらつらと述べましたが、
業務では他にも

• フレームワーク特有の関心事
• 並行処理
• データベース(performance_schemaとか..)、Queryチューニング
• 変更に強いコード設計

等々競技プログラミングだけをやっていても手に入らない知識も沢山あります。

「今後の自分がどうなっていきたいのか。」「そのためには今何をやるのが一番よいのか。」というのは自分の状態や外部の状況によって日々変わっていくものだと思います。

更に、今までつらつらと書いてきたような知識を学ぶためには絶対にAtcoderじゃないといけないかというとそうではなく、Atcoder以外のサービスでも学べますし、自分で選んだ本を読んだり興味があるOSSにContributeしてみたりするのもいいと思います。

「競技プログラミングだけをやっていれば幸せになれる」とか「競技プログラミングなんてやるだけ無駄」といった片方に寄った視点ではなく、その時その時に必要なインプットは何なのか。ということを常に考えていきたいですね(自戒)。

競技プログラミングばっかやってrubyから逃げるな自分

おわりに

Atcoderはとっつきやすくて、周りにも勧めやすいですし、私は今アルゴリズムやデータ構造の勉強が非常に楽しくAtcoderを始めてよかったな~と心の底から思います。

今後もしばらく土曜日はビールやハイボールの魔力を振り切りコンテストに出つづけたいと思います。
🍻🍻🍻🍻🍻🍻🍻🍻

目指せ水色コーダー！

当時読んだ資料や本等を適宜見直しながら書きましたが、もし私の理解が浅く間違った記述をしておりましたら、コメント等で教えていただけますと幸いです。

脚注

1. https://argoproj.github.io/argo-workflows/walk-through/dag/

2. https://github.com/ridgepole/ridgepole/blob/1.2/CHANGELOG.md#083

3. ワイ「Googleのコーディング面接で使えるかもしれないKosarajuとTarjanアルゴリズムを教えて？」

4. BlackHat GraphQL (Nick Aleks, Dolev Farhi) Chapter.5 Denial of Service

5. Algorithms and Data Structures for Massive Datasets (Emin Tahirovic, Dzejla Medjedovic, Ines Dedovic) Chapter.2 Review Of Hash Tables And Modern Hashing With high probability, the fullest bin will have O(log n/log log n) balls (http://mng.bz/QWjm); hence the longest chain in the chaining method is no longer than O(log n/log log n), giving an upper bound on the lookup and delete performance.