AtCoderで入緑しました
はじめに
どうも、Qemelly（けめる）です。今回はARC164にて緑レートに到達したので、入緑記事を書いていこうと思います！
ギリギリなので次のABCで落ちるかもしれませんが、1度でも緑に到達したということでご愛敬。
スペック
- 落ちこぼれ大学生
- 2022年春に入院、やることないのでAtCoder始めるもそこまでハマらず
- そのまま1年経過、春休みにUnity開発を始め、その流れで競プロも再始動
- 真面目にやり始めたのは3月、入緑達成は7月
- 使用言語はC++→C#
⭕️ やってよかったこと
一言で
『競技プログラミングの鉄則』のA問題をやり込もう！
本を購入
言わずと知れた入門本『競技プログラミングの鉄則』です。正直言って、これをマスターすれば入水も狙えると思うくらいには有用な書籍です。オススメです。
https://www.amazon.co.jp/gp/product/B0BDZGDM9J/
本の問題の精進（競技プログラミングの鉄則 演習問題集）
『競技プログラミングの鉄則』はAtCoder上で回答できるため、それを進めながら解説を読む作業を続けました。現在合計70問程度解き切りました。(A問題ヒューリスティック以外ほぼ全部、B問題ちょっと)
アルゴ式
わかりやすいです。理解しづらい部分だけやっていくのがオススメですが、体系的にやってもいいかも。
AtCoderProblemsのBeginner's BootCamp
レート400くらいのときにやってました。確かに有用ですが、『競技プログラミングの鉄則』を進めた方がいいと思います。そのくらいあの本には良問が多い。
ノートに整理
タグ付きでNotion(現在はObsidian)に解いた問題を整理していました。
以下のような使い方が期待できます。
- 方針が分かっているけど実装が分からないときにタグ検索で着想を得る
- 方針が分からないときに同レート帯のアルゴリズムを眺めて使えないか考える
要するにいつでも使えます。精進の際にも役立つので、ノート整理は有効です。
ノート整理の際は、書籍中の類題を探して関連付けます。こうすると問題に対する勘所がつかみやすくなると思います。
ただ、時間の掛け過ぎには注意。
❌やらなくてもよかったこと
競プロ典型90問
最初にやるには難易度が高すぎました。また、問題が包括的にまとめられている感じが薄いです。
お金を出せる方は『競技プログラミングの鉄則』でいいと思います。
レート400くらいの頃のARC参加
120分かけて1問も解けない時間が少し勿体ないです。レートもまず上がりません。
その時間に別の問題を精進した方がいい気もします。
毎日精進
単純に疲れます。
解かない日があってもいい。けんちょんさんの解説記事を読んで満足する日があってもいい。
入緑に必要なアルゴリズム
☆→○→△→×
| アルゴリズム等 | 必要度 | 自分の実力 |
|---|---|---|
| やるだけ問題の実装力 | ☆ | △ |
| bit全探索 | ○ | ○ |
| 順列全探索 | △ | ○ |
| 二分探索(めぐる式) | ☆ | ○ |
| 整数問題系*1 | ○ | △ |
| 累積和(2次元含む) | ○ | ○ |
| しゃくとり | △ | △ |
| greedy法 | ○ | △ |
| BFS | △ | ○ |
| DFS | ☆ | ○ |
| DP | ○ | △ |
| map | ○ | ○ |
| set | ○ | ○ |
| queue/stack | △ | △ |
| priority_queue | △ | △ |
| union_find | ☆ | ○ |
| ダイクストラ | × | △ |
| ワーシャルフロイド | × | △ |
| segment_tree | × | × |
| ダブリング | × | × |
- 何よりも実装力が大事な気がします。dpでindex1つズレたり、NとMをtypoしたり、dfsで無限ループしたり、二分探索書き間違えたり...
- こういったミスを減らすにはノートに傾向をまとめたり、問題を解く量を増やしたりすることが必要です
- 次点で大事なのはDFS、二分探索、union_find辺り。
- データ構造も大事です。map/set/stack辺りを知っておくと、C問題の正答率が上がります。
- 整数は特殊なので、地道に練習あるのみ...
整備しておいた方がいいライブラリ
手書きできるに越したことは無いですが、コピペして使えるライブラリを持っておくことも有効です。
