はじめに
皆さんこんにちは、 Ryusuke です。
競プロアドベントカレンダー 2022 の最終日の記事です！
今年は初めて主催しましたが皆さんのおかげで全ての枠が埋まりました！
本当にありがとうございました！
AtCoder に取り組み始めて2年半で念願の水コーダーになれました！
今回はその水コーダーになるまでに取り組んできたことやお気持ちを表明していきたいと思います。
自己紹介
所属：公立はこだて未来大学システム情報科学部 B4
AtCoder：https://atcoder.jp/users/ryusuke_h
Twitter：https://twitter.com/ryusuke__h
GitHub：https://github.com/ryusuke920
はてなブログ：https://ryusuke920.hatenablog.jp
OMC：https://onlinemathcontest.com/users/ryusuke_920
Qiita：https://qiita.com/ryusuke920
Twitter には基本毎日います。
フォローして僕から得られるものは何一つありませんが、もし興味のある方はどうぞ。
水色の実力・評価
水コーダーの実力は AtCoder 社長の chokudai さんが以下のように評価しています。
水色はかなり優秀です。普通に企業とかで超優秀って言ってるプログラマが居た時に、半分くらいはこのランクになると思います。数学が得意なタイプだと、この一つの上の青色に行きますが。
半数以上のIT企業において、アルゴリズム能力についてはカンストと言えるでしょう。特にアルゴリズム的な能力を必要としない会社であれば、ここから上はレートを上げても実務に役立つ部分はほとんどありません。
※AtCoder（競技プログラミング）の色・ランクと実力評価、問題例より引用
半数以上のIT企業でカンスト！！嬉しすぎるコメントですね
一応、他の色の実力も載せておきます。
| レート | 色 | 実力 |
|---|---|---|
| Rating - 399 | 灰 | １回参加するだけでなれるので実力の保証は全くない |
| 400 - 799 | 茶 | AtCoder 内だとあまり高くはないが一般的には十分なレベル |
| 800 - 1199 | 緑 | 学生ならかなり優秀 / エンジニアとしてもある程度の安心感がある |
| 1200 - 1599 | 水 | 半数以上のIT企業において、アルゴリズム能力についてはカンスト |
| 1600 - 1999 | 青 | アルゴリズム力はカンストしており、一部企業においては持て余してしまう |
| 2000 - 2399 | 黄 | 研究職・研究開発などや、高度なアルゴリズムを要求される開発現場で重宝される |
| 2400 - 2799 | 橙 | 検索サービスなどの滅茶苦茶アルゴリズムが大切な会社・研究開発でないとアルゴリズム力を活かせない |
| 2800 - | 赤 | 化け物しかいない / chokudai社長はここです |
こんな感じで遂に折り返し手前まで来たのかという気持ちです。
学んだアルゴリズムについて
次に水になるまでに学んだアルゴリズムを紹介していきます。
マークは以下のような判断で書いています。
| マーク | 説明 |
|---|---|
| ◎ | 1から全て実装できる上に、ライブラリも整理しており、さらに問題ごとに適切な工夫が施せる |
| ○ | ライブラリを置いてあるので、中身を理解できていないことが稀にあるが、ある程度使いこなすことは可能である |
| △ | アルゴリズムを理解はしているが、工夫が必要な問題になると苦戦することがある |
| × | 聞いたことない・調べながらでないと実装できない・使いこなせない |
茶 列は入茶した際の理解度、緑 列は入緑した際の理解度、水 列は入水した際の理解度を示しています。
過去の色変記事
ちなみに過去の色変記事はこちら！
入茶記事
入緑記事
見ていただければわかりますが、緑 ➡ 水で学んだアルゴリズムが大量にあるので、分野別に表にしています！
グラフ
| アルゴリズム | 茶 | 緑 | 水 |
|---|---|---|---|
| ダイクストラ法 | × | ◎ | ◎ |
| ワーシャルフロイド法 | × | △ | ◎ |
| ベルマンフォード法 | × | × | ◎ |
| オイラーツアー | × | × | ◎ |
| トポロジカルソート | × | × | ◎ |
| プリム法 | × | × | ◎ |
| クラスカル法 | × | × | ◎ |
| 強連結成分分解（SCC） | × | × | ○ |
探索
| アルゴリズム | 茶 | 緑 | 水 |
|---|---|---|---|
| 幅優先探索（BFS） | △ | ◎ | ◎ |
| 深さ優先探索（DFS） | × | △ | ◎ |
| bit全探索 | ○ | ◎ | ◎ |
| 半分全列挙 | × | △ | ◎ |
| 順列全探索 | △ | ◎ | ◎ |
| 二分探索 | △ | △ | ◎ |
DP
| アルゴリズム | 茶 | 緑 | 水 |
|---|---|---|---|
| 1次元DP | △ | ◎ | ◎ |
| ナップザック問題（2次元DP） | × | ○ | ◎ |
| 最長共通部分列（LCS） | × | ◎ | ◎ |
| 最長増加部分列（LIS） | × | ◎ | ◎ |
| 区間DP | × | × | ○ |
| 期待値DP | × | × | ○ |
| 確率DP | × | × | ○ |
| bitDP | × | × | △ |
| 桁DP | × | × | △ |
| 竹DP | × | × | × |
数学・幾何
| アルゴリズム | 茶 | 緑 | 水 |
|---|---|---|---|
| GCD / LCM | ◎ | ◎ | ◎ |
| 累積和（1次元） | ◎ | ◎ | ◎ |
| いもす法 | △ | ◎ | ◎ |
| 累積和（2次元） | × | ○ | ◎ |
| 素因数分解 | ○ | ◎ | ◎ |
| 約数列挙 | △ | ◎ | ◎ |
| 高速素数判定 | ◎ | ◎ | ◎ |
| エラトステネスの篩 | × | ◎ | ◎ |
| 高速冪乗計算 | × | ◎ | ◎ |
| 回転行列 | × | △ | ◎ |
| 繰り返し二乗法（ダブリング） | × | △ | ○ |
| 逆元 | × | × | ◎ |
| 拡張ユークリッドの互除法（ExtGCD） | × | × | ○ |
| 行列累乗 | × | × | △ |
| 形式的冪級数（FPS） | × | × | △ |
木
| アルゴリズム | 茶 | 緑 | 水 |
|---|---|---|---|
| 木の中心 | × | × | ◎ |
| 木の直径 | × | ◎ | ◎ |
| UnionFindTree | × | ◎ | ◎ |
| BinaryIndexedTree | × | × | ◎ |
| SegmentTree（セグメント木） | × | × | ○ |
| LazySegmentTree（遅延評価セグメント木） | × | × | △ |
文字列
| アルゴリズム | 茶 | 緑 | 水 |
|---|---|---|---|
| 座標圧縮 | × | ◎ | ◎ |
| ランレングス圧縮（RLE） | × | ◎ | ◎ |
こんな感じで精進してきました。
この中でも特に必要だと感じたアルゴリズムを 3 つ紹介したいと思います。
それは、DP, DP, DP です！
ABC が 8 問制になった後から問題数が多い分、必ずどこかで DP が出題されるような傾向になってきている感じがします。
- C, D あたりに出題される基礎的な DP
- E, F あたりに出題されるただ実装するだけでは解けないような DP
- G, Ex あたりに出題される個人的には解説を見てやっと理解できるかできないかレベルの DP
といったように、とにかくたくさんの DP が出題されている感覚です。
DP の勉強方法として有名な問題集を載せておきます。
- EDPC
EDPC は、 Educational DP Contest の略称であり、 A~Z までの 26 問が全て DP の問題となっています。
この問題を全て完璧に解ければ青, 黄レベルの DP であればほとんど解けるようになると思います
- TDPC
TDPC は、 Typical DP Contest の略称であり、 A~Tまでの 20 問が全て DP の問題となっています。
EDPC よりもさらに難しい問題が用意されており、僕自身も全然解けていません...
おそらくですが、この 2 つを全て解けば ABC で出題されるレベルの DP にはまず迷わなくなると思います。
精進量
次に、水コーダーになるまでの軌跡・精進料について紹介していきます。
Achievement
AtCoder のみで 2000 問近く解いていたのは驚きでした。
yukicoder, AOJ, paiza, TechFUL など他のサイトでも結構な量の精進をしたので全て合わせると 3000 問は余裕で超えていると思います。
ABC
G, Ex についてはほとんど解いていないかったので載せていません。
水になるには個人的には以下の 2 点が重要だと思います。
- D 問題までを安定して解けるようになる
- 得意分野を作って、その分野に対しては E, F でも 50 % くらいで解けるようになる
D 問題までは比較的 緑 diff 以下の問題がほとんどです。なので水コーダーを目指すのであればここはほとんど落としてはいけません。
また、E, F は同じ配点で 500 点となっていますが、最近の傾向では明らかに F 問題の方が難しいです。
ですが、コンテストの終了後に復習がてら得意分野であれば F 問題以降にも解説を参考にしながら解くことをオススメします。
Difficulty
水 diff に関しては半分くらい解いていました。
青以降の精進量が圧倒的に足りないので今後、青を目指すのであればまだまだ精進する必要がありそうです...
Language
基本 PyPy, Python を使用していますが、最近 C++ を勉強し始めました。
理由としては以下の通りです。
- 強い競プロer は全員 C++
- ICPC で自分だけ Python なので C++ もある程度は読み書きできた方がいい
- 使える言語を増やしたい
全て理にかなっていると思います。
お気持ち表明
さて、ここからが個人的に読んでいただきたいお気持ち表明です。
【競プロ】というテーマでお気持ちを表明していきます。
メンタルが弱い方は、周りと比べてはいけません
競プロを行う上で、なるべく周りと比べてはいけません。
競プロ垢を作って 3 年になりますが、周りが強すぎて自分だけレートが上がらずに精神的に疲れて引退していった方を何人も見てきました。
僕自身は比較的メンタルが強い方だと思っているので、周囲にそのような人がいても「追いつきたい！」とか、「流石にあの人はレベチだ。どんどん強くなるのを応援しよう！」みたいに捉えるので病んだことはありません。
とにかく自分が楽しく競プロをできる環境にしましょう。
そもそも週末に毎回時間を取って、コンテストに出場しているだけで立派だと思います。
レートを上げたい方、streak 続けるのって意味ありますか？
これは入緑記事の際にも書いたのですが、レートを上げたい方の streak を続ける取り組み方は、 個人的には（ここ大事） オススメしません。
というのも、自分も元々は longest streak 勢でしたが、320 日を過ぎたある日を栄に切れてしまいました。
streak を繋ごうとすると、自分にとって簡単な問題で繋ぐことが比較的増えるため、レートを上げる練習にはほとんどなりません。
早解きの練習になるという意見もありますが、競プロは点数が優先されるため、例え 1m で A, B, C を 3 完しても、 100m で A, B, C, D の 4 完をした人には負けます。
難しい問題を練習していればそれよりも簡単な問題は必然的に早く解けるようになるはずなのであまり負荷をかけて毎日 streak を繋ぐのはメンタル的にもオススメできません。
これはあくまで個人の見解なので、それがモチベになっている、これが競プロの楽しみです、という方を否定するつもりは全くありません。
ただ、毎日精進しているけどレートが上がらない、という方は良ければ参考にしていただければ幸いです。
エンカ楽しい
今年の夏休みに初めてリアルで競プロ er の方々と合計 4 名エンカしました。ご飯食べながら競プロの話をしたり、大学・仕事の話をしてとても盛り上がりました。
エンカするのが怖い方もいらっしゃるみたいですが、競プロer はほとんどの方が優しい方なので勇気を出してエンカしてみるととても楽しかったりします。
P.S 函館にいるので函館に観光しに来た方は是非ご連絡ください！！車もあるのでタクシー代浮きますよ。
Twitter を使おう
競プロer はツイ廃が多いです（ある方の引用）。日常的なツイートもあれば、コンテスト終了後には解法についてツイートする場合もあります。
わからないことがあれば質問すれば比較的誰かしら答えてくださいます。
みんなも Twitter を使おう。
最後に
AtCoder を始めて以来、ずっと目標にしていた水色についになることができました...
ガチの最終目標は 黄色 コーダーを目指しているので、今後も精進を欠かさず行っていきたいと思います。
最後まで読んでいただきありがとうございました。