はじめに
タイトル通りですが緑になりました。これから目指す人の参考になればと思い、この記事を書きます。
https://atcoder.jp/users/mokrai
やったこと
1. 『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』(https://book.mynavi.jp/ec/products/detail/id=35408)
書籍です。緑になるために必要でない情報も含まれているので、最速で緑になるために必要かと言われたら微妙ですが、これまで学校等でアルゴリズムを学んだことが無い自分にとっては大変勉強になりました。体系的に学べたのが良かったです。
2. ひたすら過去問を解く
私の実績はこんな感じです。(緑になってから1週間後くらい)
まず、ABCのC問題を埋めていきました。AtCoder Problemsで各問題のdifficultyを見て、簡単な問題から解いていきました。水色以上の問題は、適度な難易度では無いと判断して解いていません。
その後は、ARCのA問題を埋めました。こちらもdifficultyが緑のものまでです。
さらにその後は、ABCのD問題を解きました。こちらもdifficultyを見て、簡単な問題からです。10問くらい解いたところで、緑になりました。
最近では(2020年1月現在)、緑パフォを出すためにはABCのコンテストで3完(ABC)は必須で、4完(ABCD)が必要な場合もあります。
したがって、「C問題は確実に解ける。D問題も頑張れば解けるかも」くらいになっておく必要があります。
3. たくさんコンテストに出る
ratedのコンテストは、特別な予定がない限り出るようにしていました。
コンテストに慣れるため、集中して問題を解く時間を作るため、コンテストへの参加回数が少ないとレーティングにマイナスの補正がかかるためです。
コンテスト後は必ず解説動画を見て復習をしました。解けた問題は自分の実装が想定回答かと別解がないかを確認し、解けなかった問題は動画を見ながらACしました。
緑が見えてくるまではC問題まで、緑に近づいてからはD問題までについてです。
解説PDFにも目を通していましたが、こちらは動画よりも内容が難しかったので、参考程度に見ていました。(すべて理解できなくてもOK)
やっていないこと
1. 蟻本
内容が難しそうで、緑になるためには不要そうだったのでやりませんでした。
2. AtCoder以外のコンテスト
AtCoderで十分な問題量があり、やっていません。
緑になる上で必要な知識、アルゴリズム
- 全探索
- bit全探索
- 二分探索
- 必要に応じて優先度付きキューが使える
- 簡単なDFSとBFS
- 簡単なDP
- 素数判定
- 素因数分解
- 累積和
- しゃくとり法
- GCD(最大公約数)とLCM(最小公倍数)が求められる
最後に
緑になるためには、センスやひらめきは(あまり)必要ないと思います。
基本的なアルゴリズムを身につけた上で、問題文を理解し、適切なアルゴリズムをバグなく実装することが重要です。
多くの良問(つまりAtCoderの過去問)に触れ、一つずつ知識を増やしていくのが近道だと思います。
以上です。