先日行われたABC297で緑色になれました。
先達の記事に多くを学び助けられたので、私も色変記事を書きたいと思います。
使用言語など
C++(gcc), Windows, WSL2 + VS Code
結構昔にAtCoderを始めたが、全然レートが上がらなくて2年間もAtCoderから離れていました。
AtCoder Problems
学習方法
ABC
参加できるABCは(今年に入ってからは)ほとんど参加しました。逆にARCはコンテストも過去問もノータッチです。ABCの公式放送はめちゃくちゃわかりやすいのでおすすめです。解説記事は良く分からないことが多いです。
バーチャルコントスト
超おすすめです。
AtCoder Problems 上 (https://kenkoooo.com/atcoder/#/contest/recent) で、毎日毎朝毎晩何かしらのバーチャルコンテストが開かれています。自分のライフスタイルに合ったものに参加するのがおすすめです。
競プロに取り組む習慣ができます。
書籍
螺旋本は昔半分ぐらいやりました。蟻本は買ったけど何を言っているかわかりませんでした・・・。
使用したアルゴリズム・データ構造
使用頻度が高かった気がする順ですが全部重要だと思います。
- Union-Find
一時期これしかでなかった。 - std::set(平衡二分探索木)
値の追加・検索・削除がO(logN)でできる上に、（内部構造的に）ソートされているので昇順・降順にも取り出せる化け物。 - DP
(基本的な)DPは一度覚えてしまうと得点源になるので学習するのをお勧めします。EDPCなど。 - 全探索
今回のABC297Eも、「Kの上限が 2e5 」⇒「小さい順に全部並べたら全探索できるじゃん！」という着想を得ました。 - std::map
map<char, vector<int>> みたいなハチャメチャな書き方ができて非常に便利。 - BFS, DFS
D問題までで問われるグラフ系の問題は、この二つで事足りるイメージです。 - bit全探索（とbit演算）
Nの値が10とか小さいの時に、メタ的にbit全探索しそうだな～とか考えます。 - GCD
- エラトステネスの篩
- 累積和
queue, priority_queue などもよく使います。
イテレーターについての知識も必要です。
また、ラムダ式が書けると（主にDFSとかで）便利です。
ラムダ式の再帰方法が検索しても良くわからなくて困った覚えがあるのでここに軽く記述しておきます。
// DFS
auto dfs = [&] (auto dfs, int index) {
// DFSを実装
};
dfs(dfs, 0);
勉強したけどあまり使わなかったアルゴリズム
- ダイクストラ法、ベルマンフォード法、ワーシャルフロイド法
D問題までではあまり問われてないように思います。 - 二分探索・尺取り法
本番で使った記憶はないのですが、たまたまそういう回が重なっただけな気がします。
[追記]
自分で実装する二分探索はあまり使用していないが、lower_boundなどは頻繁に使用しています。
まとめ
茶色・緑の問題は特定のアルゴリズムを使用する問題もあれば、上記のデータ構造や簡単なアルゴリズムの組み合わせに帰着できるアドホック？な問題も多いです。後者を鍛えるためには数をこなすしかありません[要出典]。バチャコンに参加しましょう。
これは個人的な趣味なのですが、ぷよぷよの連鎖をシミュレートするプログラムと、謎ぷよというぷよぷよの詰将棋みたいなものの解を探索するプログラムを作ったらBFS,DFS,2次元Grid系の問題にめちゃくちゃ強くなったのでここに記しておきます（お勧めできるかどうかはわかりません）。
私も水色目指して頑張るので、みなさんも一緒に精進しましょう。