AtCoder 青になるために必要だと思う知識
内容はこじんの見解であり、(略)
レーティング推移グラフを見る限り、青になるまでに時間がかかっております。
僕は AtCoder を始めた当初から、目標は青になることでした。
そんな僕が、個人的に AtCoder 青になるために最低限必要な知識を上げてみます。
レートが上がる要因は 地頭 と 知識で 5:5 だと思っております。以下に挙げるのはあくまで必要な知識です。また、アルゴリズムの細かい解説は Google 先生に任せます
- imos 累積和
- DFS BFS
- 二分探索 尺取り法
- 貪欲法
- DP
imos 累積和
区間を扱う問題で威力を発揮します。
累積和は 2 次元のものも知っていたほうがいいです。
DFS BFS
グリッドに対する探索や、グラフ上の探索、など様々なパターンが考えられますが、
全探索は全てのアルゴリズムの基本だと思います。
グラフに限らず、以下のような問題対して全探索の気持ちになれるといい感じだと思います。
二分探索 尺取り法
概念から実装まで、しっかり理解することが大事だと思います。
高得点の問題でも要求される考え方のように思います。
貪欲法
難しいです。
貪欲に何かをすることの最適性をプチ証明する練習をするといいかもしれません。
DP
これが一番大事といっても過言ではありません。状態の遷移を考えることがキモだと思います。ここで、DP の次元は本質ではないです
まとめ
青になるために最低限必要な知識をまとめてみました
思ったより少ないですね！
