こんにちは。Natsuです。
読んでいただき、ありがとうございます。
今回はAtCoderで緑色になれた！！ということで初の色変記事を書いています。
ついに念願の緑入りしました！！競技プログラミング始めて８ヶ月、頑張ったかいがあった
— Natsu Ozawa (@ntszw) November 22, 2020
natsuozawaさんのAtCoder Beginner Contest 184での成績：973位
パフォーマンス：1522相当
レーティング：707→826 (+119) :)
Highestを更新し、6 級になりました！#AtCoder #ABC184 https://t.co/sUsZf9Z3Uv pic.twitter.com/HNVIDVikTq
というのも、Qiitaやhatenablogには勉強面で素晴らしいアドバイスを下さる記事があるのですが、自分は競技プログラミングに対する意識の面で欠けていました。
滅茶滅茶やばい、遂にコンテストで１完さえもできなくなった pic.twitter.com/bXar096Xdd
— Natsu Ozawa (@ntszw) October 24, 2020
実際にグラフを見てもわかる通り、僕は十月の頭ぐらいから成長が伸び悩み、レートが落ちてしまいました。これをどう対処し、V字回復に持っていたかを中心にお話をしたいと思います。
画像出典：AtCoder Performances
停滞する前までにやっていたこと
はじめにですが、意識だけでレートは上がらないので、基本的なアルゴリズムと高校数学の知識は必要だと思います。僕はレートが停滞するまで、ずっと知識系の勉強をしていました。
- E869120さんの過去問精選１００問をひたすら埋める。
- 上の記事に書いてあったアルゴリズムを一通りウェブの記事などで勉強。
アルゴリズム学習にはけんちょんさんの記事と、アルゴリズムロジックに頼りました。
僕は高校数学Aを履修したことがないので、重複組み合わせなど出題された知識はその都度ネットで調べました。
次の表をざっと見ていただければ分かるのですが、正直緑色に必要のないものまで勉強していました。また、コンテスト中に一から書いていると実装ミスが起きるので、便利なC++標準ライブラリの使い方をある程度覚えるようにしていました。分からなかったらコンテスト中にCPP Referenceにのっている実装例を真似しました。
| アルゴリズム・テックニック | 頻度 | 応用 | ライブラリ |
|---|---|---|---|
| 全探索 | ◎ | ほとんど全部 | |
| 順列全探索 | △ | next_permutation |
|
| ビット全探索 | 〇 | bit DP | __builtin_popcount() |
| 二分探索 | ◎ |
lower_boundなど |
|
| 深さ優先探索 | ◎ | グラフ、特にグリッド | |
| 幅優先探索 | ◎ | グラフ問題全般 |
queue,deque
|
| ダイクストラ法 | △ | priority_queue |
|
| ワーシャルフロイド法 | △ | ||
| クラスカル法 | △ | union find(コピペライブラリ） | |
| ナップザックDP | ◎ | ||
| Bit DP | × | ||
| 区間DP | × | ||
| 素数計算 | 〇 | エラトステネスの篩 | |
| 約数計算 | ◎ | set |
|
| 逆元計算 | ◎ | ||
| 累積和 | ◎ | いもす法 | |
| Union find | 〇 | クラスカル法 | コピペライブラリ |
ただ、アルゴリズムや数学を勉強しているだけでは緑には届きませんでした。当たり前なのですが、僕は皆さんの色変記事を読んでそれに気づきました。
AtCoder Shojin
ということで１１月上旬から僕は過去問をやることにしました。最初はなかなか気が向かなかったので、AtCoderの精進状況を管理するためのツール、AtCoder Shojinを作ろうと思いました。ですが、HTML書くのも面倒くさいので、Notionに自分用のAtCoder Shojinページを作りました！！（本当はExcelでもよかった）
じゃーん。Linux環境の問題で日本語が打ちにくいので英語になってます>.<
それぞれの問題に対して、解くのにかかった時間、デバッグで突き止めた問題、再発防止策や使えそうな考え方などを記録しておきました。
例えば、64ビット整数同士の計算でオーバーフローしてしまった、などのミスを問題の欄に書き込みました。その次に、何を意識していればミスを予防できたかについて考え、再発防止策の欄に書き込みました。例えば、「32ビット整数以外でもオーバーフローが起きることを予測する」などです。また、再発防止策が実際に役立った場合や、同じミスを犯してしまった場合などで重要だと思ったものは、太文字にしました。
デバッグで検討がつかなくなったとき、この一覧を見返して何か忘れていないか確認することができます。（ミスを記録することで、この表を見なくても大抵そのミスが発見できるようになりました）
自信をつける
あとは、過去問を解いて自分が緑色レベルだという自信をつけました！
僕はABCのD、E問題のうち茶色上位～緑色上位の問題を中心に解きました。AtCoder Problemsで「Recommended」に出てくる問題なら「Difficult」（つまり、茶色上位～緑色の問題）を解くと良いと思います。
実際に解く
難しい問題なので、ぱっと解法が浮かばないのが当たり前です。それでも、最後に自分で解法を導けた、という経験を積むことが大事だと思います。
白紙を取り出し、慎重に問題をイメージ化します。例えば、グラフだったら（特殊ケースでない）例のグラフを実際に描いてみる、数列だったら例の列を書くなどします。
このあと、自分が手動でこの問題を解くとしたらどのようにして解くかをヒントに、解法を考えます。分からないときは、今まで自分が勉強してきたアルゴリズムや典型テクニックを当てはめることができるかを考えるのも良いです。
このように紙面で実例を考えると、解法の実装が簡単になりました。例えば、DPや累積和の漸化式などは、いつも実例をもとに作成しています。
困ったとき
ある程度経ってもアイディアが全く浮かばない場合は、解説ACを目指す派です。ACした後には、どのように考えれば解けたかをShojinテーブルに記述しました。決して落ち込んだりせず、自分が新たなテクニックに出会えたことを寧ろ喜ぶことを意識しました。
長い間デバッグしても直らないときは、時間の無駄なのでAtCoder's Testcasesから入力を拾ってきて解決しました。そして、ミスの原因と予防策をShojinテーブルに記録しておきました。
解けたとき
難しい問題が解けたということは、自分が成長しているということです！実際のコンテストでもD、E問題が解けるという自信の根拠になります。
時間がかかったときは、何をすれば時間を短縮できたかを改善策の欄に書き込みました。
前に自分が解けなかった問題を解いてみる
ある程度自信をつけた後、コンテスト中に自分が解けなかった問題を解きました。
コンテスト本番
舞を踊る
でもこれ本当に大切で、水パフォをとるくらいの気持ちで臨まないといけないと思います。
まとめ
大雑把に言うと、自分の能力に自信を持つことが一番だと思います。そのために、過去問を解いて経験を積み重ねました。ACしたときは成長したという自信、解説ACしたときは学習したという自信です。"I never lose; I either win or learn”（と誰かが言ってた）ように、精進して弱くなることはありません。ということで、お互いこれからも競技プログラミングを楽しみましょう！！