1. 概要
2022年2月にAtCoderの水色になりました。
この記事では、AtCoderで水色になるまでに行ったことと、8問体制で水色になるために必要と思われることをまとめます。
2. 準備
私について
私は学生時代にTopCoder等で少し競技プログラミングを経験していました。十数年ぶりに競技プログラミングを再開し、昨年からAtCoderを始めました。そのため事前知識がある状態からスタートし、最初は水色を目標としました。
言語はC++を使うことが多いですが、Pythonの方が解きやすそうな場合はPython3を使います。
環境構築
PCの準備
Linuxで開発したかったので、デスクトップPCと、別用途で契約していたVPS上に開発環境を構築しました。性能が高くないVPSでも開発には十分でした。どのノートPCからでも慣れた環境で開発できるのでVPSは便利でした。
開発ツールの準備
TopCoderでの経験で、テストや提出用のツールがあると大きく効率化できることを知っていましたので、AtCoderでもツールを導入しました。atcoder-cliを使っています。
GitHubリポジトリの準備
ライブラリや、解いた問題を記録するためのリポジトリを準備しました。解いた問題はすべてリポジトリに登録しているので、登録量が増えることによってモチベーション維持になります。また、デスクトップPCとVPSでライブラリを同期するにも便利です。
3. 取り組み
勉強とライブラリ整備
TopCoderでの経験で、ライブラリを作っておくことの重要性は知っていましたので、まず初めにアルゴリズムとデータ構造の復習とライブラリ化から取り掛かりました。使った本は以下の2冊です。
1冊目はネットワークフローまで読み、ライブラリ化しました。Union-Findが必要な場合等でライブラリが役立ちます。グラフ探索等もライブラリに登録しておき、ライブラリを確認しながら問題を解いています。2冊目は計算幾何学のアルゴリズムが載っていることが特徴です。必要な時に参照しています。
次に、初中級者が解くべき過去問精選 100 問を解きました。本で勉強したアルゴリズムやデータ構造を演習する他、べき乗や逆元、二項係数の高速な計算法等、足りないライブラリを追加しました。
その後、ここまでに現れなかったbinary indexed treeやセグメント木をライブラリに追加しました。今のところ、水色レベルでは以上のアルゴリズムとデータ構造で足りています。
コンテストに参加して8問体制のF問題まで解く
AtCoder Beginner Contest (ABC)はほぼ毎回参加しました。分からなかった問題は、F問題まで、解説やYouTubeの解説を見て、ACを出すまで復習しました。
コンテストの復習でも、過去問を解くときも、8問体制のF問題まで解くようにしました。最初の頃はE問題まででしたが、伸び悩んでE問題では足りないと分かったので、途中からF問題まで埋めるようにしました。F問題を解くのに必要な知識を知っていればE問題の解法を思いつくことも多かったので、F問題を解くようになってから徐々にコンテスト中にE問題まで解けることが多くなったと思います。
なお、参加するだけで一定数の問題パターンに触れられますので、毎回参加して良かったです。
Educational DP Contest (EDPC) を解く
E問題以上の動的計画法が解けないことが多く、伸び悩んでいたので取り組みました。最後の方はまだ解けていません。動的計画法の基本パターンが学べますので、E問題で出るような少しひねった動的計画法に対する安定度が上がったと思います。
4. 水色になるために必要なこと
私が8問体制で水色になるために必要だと思ったことをまとめます。
8問体制のコンテスト中にE問題まで安定して解くこと
8問体制になってから、コンテスト中に何問ACすれば水色になれるかの情報があまり無く、最初のうちは困りました。8問体制がある程度進んでからは、A~C問題までで茶色、A~D問題までで緑、A~E問題までで水色が目安だと分かったので、そこからはE問題を解くことを目標に取り組みました。
E問題を解くために必要な知識
初中級者が解くべき過去問精選 100 問で挙げられていたアルゴリズムとデータ構造の知識が必要です。私はこれを知っているだけではD問題までで伸び悩んでしまいました。これに加えて、E問題を解くには以下が必要だと思いました。
- アルゴリズムやデータ構造の導出
例えば、ワーシャル・フロイド法のdp変数や、クラスカル法の各ステップの意味、Union-Findの動作中の各変数の意味です。導出を知っていると解法を思いつくことがあります。 - 有名問題の知識
射撃王、平面走査、区間スケジューリング等です。AtCoderの解説等で紹介された有名問題は解くようにしました。有名問題を知っていると解法を思いつくことがあります。
5. 勉強量のデータ
勉強時間
疲れていない日は、毎日1~2時間くらい取り組みました。コンテストを除いて、平均して毎週4~5日だったと思います。
解いた問題数は、1週間にE~F問題を1~2問とEDPCを1問くらい（コンテスト中を除く）でした。
どのくらいで解説を見るか？
分からない問題があった場合、その日のうちは考えて、解説を見るのは翌日以降にするようにしていました。（コンテスト中にじゅうぶん考えて分からなかった問題は、コンテスト後に解説を見ていました。）
6. 余談
私の学生時代は”蟻本”の初版が発売されていなかった頃で、競技プログラミングをする上で必要な知識を体系的に学ぶことが難しかったと記憶しています。また、コンテストも英語のみだったので、参加するハードルが今よりも高かったです。
今は競技プログラミングを学ぶのも参加するのもしやすい環境になっており、とてもありがたかったです。