AtCoderで青色になったので2年間を振り返ってみた
はじめに
1/23のABC189で、青色になることができたので、例に倣って色変記事を書いてみました。少しでも誰かの参考になれば嬉しいです。
AtCoderとは
AtCoderはプログラミングコンテストを開催しているサイトです。ほぼ毎週コンテストが開催され、約1万人程度の参加者が参加します。問題が6問ほど出題されるので、データ構造やアルゴリズム、数学などを使って解法を考え、その解法を実現するプログラムを作成することで競います。
レートに応じて色が割り振られ、下から順に灰・茶・緑・水・青・黄・橙・赤となっています。各色の詳しい評価は下の記事に書かれています。
chokudai.hatenablog.com
競技プログラミングを始めるまで
某地方国公立大の電気情報系の学科に通っています。大学入学前はプログラムを書いたことも見たこともありませんでした。他の方の色変記事を見るに、恐らく青色になった人たちの中では平均~少し多いくらいの精進量ではないかと思っているので、天才や化け物の類ではありません。
大学が始まるまでの春休みにプログラミングを始めてみたいと思い、DXライブラリでSnakeや2048、テトリス等の簡単なゲームを作ってみました。プログラムのロジックを考えることや、計算した結果が画面に出力されることはとても楽しかったのですが、正直Unityなどで本格的にゲームを作ることには興味を感じられませんでした。
その後、同じ学科の友人に競技プログラミングに誘われて始めて見たところ、好みにドンピシャで、楽しすぎてやめられなくなってしまいました。
茶色になるまで(~1回生7月)
自分の書いたプログラムが動いて結果が出てくるのが楽しくて、ABCのA~B問題をたくさん解いていました。文字列の扱いにかなり苦戦していたのを覚えています。
ちなみに、初めて知ったアルゴリズムは累積和でした。友人に教えてもらい、すごく感動したのを覚えています。その他、灰色の間に勉強した内容は以下のものがありました。
配列 | ソート | 累積和 | bit全探索 | ナップサック問題 | 幅優先探索 | 深さ優先探索 |
茶色になるまでに解いた問題数です。(その他はdifficultyのついていない問題、CFはCodeforcesの略です。2021年1月25日時点の問題数を母数としているので、割合は当時のものではありません。)
diff | 灰 | 茶 | 緑 | 水 | 青 | 黄↑ | その他 | CF | 合計 |
---|---|---|---|---|---|---|---|---|---|
AC数 | 217 | 11 | 5 | 2 | 0 | 0 | 9 | 0 | 244 |
割合 | 40% | 6% | 3% | 1% | 0% | 0% | - | - | - |
緑色になるまで(~1回生10月)
コンピュータについて全く無知でしたので、情報の分野全体の広い知識が欲しくて、夏休みはIPAの応用情報技術者試験の勉強をしていました。AtCoderのおかげで、午後のプログラミングの問題がとても楽になりましたし、逆にこの資格の勉強のおかげでデータ構造の理解が進んだこともありました。
10月ごろ、他大学の競プロ仲間ができて、お互いに作問した問題を解き合ったりしていました。作問は理解が深まるので、とてもお勧めです。そこのメンバーが異常精進をして信じられない速さででレートを上げているのを見て、「強い人はこんなに精進しているのか!」と、とても良い刺激を貰いました。
この頃は基本的には灰~茶diffをひたすら埋めながら、時々蟻本初級編の類題を解いていました。
qiita.com
緑になるまでに勉強した内容とAC数は下の表のとおりです。
逆元 | 二項係数 | GCD, LCM | 約数列挙 | 素数判定 |
素因数分解 | 素数列挙 | 二分探索 | 尺取り法 | imos法 |
繰り返し二乗法 | 拡張Euclid | 凸包 |
diff | 灰 | 茶 | 緑 | 水 | 青 | 黄↑ | その他 | CF | 合計 |
---|---|---|---|---|---|---|---|---|---|
AC数 | 294 | 78 | 30 | 3 | 0 | 0 | 9 | 0 | 414 |
割合 | 54% | 42% | 16% | 2% | 0% | 0% | - | - | - |
水色になるまで(~2回生6月)
緑diffを埋めたり、引き続き蟻本初級編の類題を埋めていました。レートが1000を超えたあたりからは、水diffで解けそうな問題を解いたり、蟻本中級編や下のサイトの問題を解いていました。コンテストでは緑diff以下を速解きして、たまに来る水diffの数学問題をACすることでレートを稼いでいました。
qiita.com
水色になるまでに勉強した内容です。
集合 | 多重集合 | 連想配列 | 順列列挙 |
優先度付きキュー | 二次元累積和 | Union-Find木 | ダイクストラ法 |
ベルマンフォード法 | ワーシャルフロイド法 | 順列列挙 | 3分探索 |
トポロジカルソート | 半分全列挙 | LCS | LIS |
diff | 灰 | 茶 | 緑 | 水 | 青 | 黄↑ | その他 | CF | 合計 |
---|---|---|---|---|---|---|---|---|---|
AC数 | 473 | 157 | 147 | 88 | 27 | 3 | 43 | 0 | 938 |
割合 | 87% | 84% | 81% | 45% | 13% | 1% | - | - | - |
青色になるまで(~2回生1月)
青は化け物だと思っていたので、この時点で競プロをやめようかと思っていたのですが、レートが伸び悩むまでは続けてみることにしました。
この時点での強みは、
- 緑diff以下の問題の解法を思いつくまでが速い
- 算数・数学的な問題が少し得意
という点でした。逆に弱みは、
- 精進時間が青を目指す割に少ない
- 実装をバグらせて時間を溶かすことが多い
- コーナーケースを見落とすことが多い
- 高難易度を解く考察力が身についていない
という点でした。コンテストで事故ってレートを大きく下げてしまうと、取り返すのに数週間~数か月かかってしまう上に、何よりモチベーションが失せてしまうことが怖かったので、特に弱点を克服していく感じで精進していきました。
まず、精進時間に関しては、Twitterの精進用アカウントを作って、生活に競プロを侵食させていきました。また、某ウイルスの影響で大学の講義がオンライン授業になり、1週間のどこでかで課題を提出すればいいという感じになったので、月・火(・水)曜日くらいに課題を一掃して、水~日曜日は出来るだけ競プロに集中するようになりました。
2・3番目の実装力に関しては、JOIの過去問を解いていくようにしました。JOIの問題は実装が重たいものが多いため、実装力を付けるのに向いています。僕の場合、実装をバグらせる主な原因は、頭の中で考察をして紙に整理しなかったり、「いける!」と思ったらコードを書きながら考察をしてしまうことでした。実装をバグらせることが多いと思ったら、コードにする前に考察を紙に整理すべきだと思います。「コードを書いている途中に考察が間違っていることに気が付いた」ということが減りますし、細かい条件分岐やコーナーケースにも注意しやすくなります。
4番目の高難易度の問題に関しては後述していますが、週に何問かだけでも青diffを埋めていくようにしました。最初は全然解けませんでしたが、次第に自力でACできる割合が増えていくのが実感できました。また、今まで勉強しなかったデータ構造・アルゴリズムもとにかく貪欲に勉強していくようにしました。
その他には、AtCoder Problemsの「くじかつ」という毎日夜9時に開かれているバーチャルコンテストに出るようにして、速解き力を鍛えたり、AtCoderの解説放送や、YouTubeでの実況、他の方の解説ブログなどを見たりもしました。特に解説放送や実況では、強い人がどんなことを考えて問題を解いているのかを説明してくれるので、とても学びが多かったです。
これらを続けると順調にレートが上がっていきましたが、11月ごろにレートが1500を超えたあたりで伸び悩みました。
典型はある程度揃っていると思っていたので、とにかく場数と演習量を増やそうと思い、Codeforcesというロシアのコンテストサイトに出たり、Educational Codeforces(通称エデゥフォ)という教育的な問題を集めたセットを埋めていくことで、無事に青色になることができました。Codeforcesは深夜にコンテストが開催されるのでおすすめはしにくいのですが、大学がオンライン授業になって、「俺が起きている時間が昼なんだ」などと考え始めている人は是非参加してみるといいと思います。
青になるまでに勉強した内容です。
Grundy数 | 座標圧縮 | 平方分割 | セグメント木 | 遅延評価付きセグメント木 |
転倒数 | 分割数 | 行列累乗 | ダブリング | ポテンシャル付きUnion-Find木 |
括弧列 | 包除原理 | フロー | 最小全域木 | 最大安定集合 |
2部グラフ | Euler Tour | TSP | Z-algorithm | Kadane's Algorithm |
区間DP | 桁DP | 木DP | 全方位木DP | Binary Indexed Tree |
Splay木 |
diff | 灰 | 茶 | 緑 | 水 | 青 | 黄↑ | その他 | CF | 合計 |
---|---|---|---|---|---|---|---|---|---|
AC数 | 546 | 186 | 182 | 181 | 116 | 11 | 196 | 157 | 1575 |
割合 | 100% | 100% | 100% | 93% | 57% | 2% | - | - | - |
その他精進について
目標の立て方について
ある程度競プロをしていると、この界隈には化け物が一定数いることがわかると思います。これはchokudaiさんも言っていたことですが、自分より圧倒的に強い人と自分を見比べて、自分を卑下するべきではないと思います。
【競プロの各色に対する認識オススメ】
— chokudai(高橋 直大)🍆 (@chokudai) June 29, 2020
・2色上は人外だと思うのが大切!比較しちゃだめ!1色上に追いついたところで人間に戻してあげよう!
・1色上は強い人!目標にするのは良いけど勝てなくて当たり前!いつかは追いつけたらいいなくらいに思おう!
・同色でも成長がヤバいやつはやっぱり人外!
まずは自分の1色上、厳しければ1級位上などを目標にしたり、あるいは今まで解けなかった問題を解けるようになったことや、コンテストで粘って難しい問題を解けたことなどをモチベーションにするのがいいと思います。
難易度の高い問題の勉強について
上で述べたような化け物以外は、色変直後は自分の色より上の問題はあまり自力でACできないと思います。これは誰でもそうだと信じたいのですが、解けないのに精進を続けることは精神的に辛いです。僕も緑になったころは水diffはほとんど解けませんでしたし、水になったころは青diffはほとんど解けなくて辛かったです。しかし、そういった難易度の問題をなんとか自力で解いたり、解説を読んだり解説放送を見て理解していくと(僕の場合は30~50問程度)、特に類題という訳でもないのに解法が見えてくるようになります。そうすると今まで解けなかった問題がだんだん解けるようになってきて、かなり楽しくなると思います。最初はしんどいですが、1週間に何問かだけでも、やる気になった時に解いていくようにするといいと思います。
下埋め(低難易度埋め)について
これは精進の方針なので、人によって向き不向きがありますし、賛否両論もあると思いますが、僕は下埋めを積極的ににやりました。下埋めは退屈ですが、やっておくとコンテストで絶対に解けないといけない問題を取りこぼすことが減りますし、速解きにも繋がると思います。実際、なりたい色の一つ下のdiffをコンテスト中にしっかり通せれば、その色のパフォーマンスが出るということはよくあります。僕は「速解きで最低限のパフォーマンスを確保してから難しい問題を落ち着いて解く」という立ち回りが合っていたので、精進では目標の色より下のdifficultyをある程度埋め終わってから、目標の色に挑戦するようにしていました。
終わりに
このまま競技プログラミングを続けるかはかなり悩んでいます。ここまで熱中できる趣味はそう見つかるものではないと思いますが、時間も大量に溶かしてしまいます。完全に私事ですが、現状一番問題なのが将来やりたい仕事が決まっていないことなので、競プロ以外の色んなことにも手を出してみたいと思っています。
そういうわけで、競プロをやめてしまうかもしれないので、残しておきたいことや記録も含めて書き連ねました。長くなってしまいましたが、最後まで読んでいただきありがとうございました。少しでも役に立ったり、共感していただける点があればいいなと思っています。