AtCoder入緑までにやったことなどです！！

はじめに…
入緑までに学んだアルゴリズム
学ぶべきおすすめテクニック・知識
1. 問題を解くためのテクニック
2. 文法的なテクニック (C++)
さいごに

はじめに…

10月26日に開催されたABC377で入緑したしべはすと申します！
この記事は入緑記念にかいた、入緑記事??とか言われるやつです！！
具体的には

緑🟢になるまでに学んだこと
知ってると嬉しいおすすめのテクニック

を紹介します！！

入緑までに学んだアルゴリズム

灰~茶色までに必要だと思うもの

全探索
二分探索
bit全探索
順列全探索
累積和
imos法
しゃくとり法
再帰関数
DFS ・ BFS ・ 01-BFS
ダイクストラ法
添え字が1つのDP
繰り返し二乗法

ここからが本題の茶～緑にかけて学ぶべきだと感じたものです

以下で、茶~緑までに学んだアルゴリズムをまとめていきます。
具体的には、”頻出だな”、”よく使う”と思ったものを☆1 ~ 10で書いていきます。
(☆の値が大きいほど、学ぶべきだと感じたものです)

二次元累積和☆8
けんちょんさんの記事がとても参考になりました!!

ABC366-Dで三次元となってでてきました…😇😇😇
↑
がDiff586のため、緑になるためには落とせないところだと思います…(私は負けましたが)
セグメントツリー🌳🌳🌳(遅延も含む)☆8
ABCでセグ木問題(緑Diff)と遭遇したこともあるのですが…当時セグ木を知らなかったため解けませんでした…最初に理解するのは難しいですが、学んでみるととても強かったのでおすすめです!!
実はABCに限らずAHCでも使えたりするので学ぶ価値大です!!!
(AHC036で筆者はセグ木を使うことでパフォ1596を達成しました…これもセグ木の力です💪)
添え字が2つのDP☆7
dp[i][j]:=i番目までで状態がjの時の~~という形な事が多いです…
ABC369-D
ABC344-D
などはこのDPができたことによりパフォが盛れて良かったです🥰🥰🥰
(DP系解けるとパフォが結構上がる気がしてます…なのでおすすめ)

“998244353で割った余りをもとめて”と言われるやつも高確率でDPで解ける問題な気がします
UnionFindとクラスカル法☆6
UnionFind…私…実はソラで書けません…
クラスカル法は名前が難しそうですが
”コストが小さい辺から見ていき、両端の頂点が別のグループに所属するならばその辺を採用する”
だけです…UnionFindさえ知っているならば覚えておくべきだと思います
ダブリング(簡単なもの(ABC167-D🟤のような))☆5
区間スケジューリング☆4
L <= RとなるLとRのペアが複数与えられるとき、Rが小さいもの順に並び替えるだけです。
O(√N)での約数列挙と素数判定☆3
どちらもO(√N)でできます。(初めて知ったときは、オオッってなりました)
どちらも同じようなコードなので、覚えておくといつか得するかも?
アルゴリズムではないけど…setとかstack。dequeなどのデータ構造を使う問題☆7
緑Diffの印象が強いです。
学びましょう

学んだけど “緑になるためには使わなさそう” な悲しきアルゴリズムたち(もちろん、どれも便利ですが…使う問題が水Diff以上な気がするんですよね…なので茶～緑の間にはあまり必要ないかも…)

ワーシャルフロイド法
(コードはめちゃくちゃ簡単ですが…ただそれを書くだけのひねりの無い問題が出るとは到底思えないので…(出るとしたら工夫が必要なムズイやつでしょう)
覚えるだけ覚えとく、ぐらいの認識でいいかも)
bitDP
トポロジカルソート
木の直径
ベルマンフォード法
これより↑は緑になるためでも、学んでいてよいかも??
区間DP
桁DP
LIS
最大流
最小費用流
SCC

学ぶべきおすすめテクニック・知識

問題を解くためのテクニック

“答えで”二分探索☆10^18
過去問を解いていても、ホントによく見かける印象です…
“~を満たす最小値”とか言われたら疑いましょう…
“bit列は各桁のbitごとに考えれる”ことが多い☆10
めちゃくちゃ頻出です
3つの値を使って何かするやつは、2つを決めて考えるとやりやすかったりする☆10
左右両方からの累積和をとったらいいやつ☆8
操作を逆順で行っても問題ない場合もある☆5

文法的なテクニック (C++)

setやmapでの最小値、最大値の取得☆10
*変数名.begin()で最小値
*変数.rbegin()で最大値
を得ることができる!!(場合によっては()で括ってあげてね)
演算子オーバーロードをできるようになろう☆10
自作クラスを比較したい問題もあるので、緑になるなら必須です!!
C++が用意してくれている機能があるならば積極的に使っていこう!!☆5
例えばABC322-Bではstarts_with()やends_with()を知っているかどうかで解く速度が全然変わってきます。

探してみると結構いろんな機能が用意されているので調べてみるとよいと思います
all_of()
any_of()
none_of()
count()
count_if()
inclusive_scan()
reduce()
あたりがおすすめです
しかし、なれるまではコンテスト中での使用は注意ですよっ
(予期せぬ文法的な罠にかかるかもですし…)
ラムダ式を使いこなそう☆1000
ラムダ式の嬉しいところ👍
1.ラムダ式の嬉しいところはキャプチャで全部を参照しちゃえば、関数の宣言時のような”使う値を引数として与える”みたいなことをしなくてよくてとても楽！！

2.コード中で何度も行う操作は、ラムダ式にまとめておくことで“タイプミスをしたことによるバグ”を減らせてとても良いです。✨✨
テンプレートを覚えよう☆1000
より柔軟なコードがかけて嬉しいです。
スニペットなどに色んな型に対応できるコードを書いておくことで、コンテスト中の時間を節約できます。