AtCoderで黄色になりました
はじめに
タイトルにもある通りAtCoderでレートが2000に到達したでのでそれまでにやったアルゴリズムとかいろいろ文章にしました。
黄色になるまでにやったこと
- セグ木/遅延セグ木
- dp
- dijkstra
- UnionFind
- 累積和/繰り返し二乗法などの初歩的なもの
セグ木/遅延セグ木について
セグメント木はソラで書けます（多分）が、遅延評価付きのセグメント木はソラで書けません。ライブラリを使っています。下にあるような記事を読むといいと思います。
dpについて
ABC-C/Dくらいでdpは頻出なのでその辺を速く書けると嬉しくなれるかもしれません。最近は添え字をミスらないようにコメントアウトでメモしています。
例
\\dp[i][j]:i番目まで見て総和がjの通り数
for(int i=0;i<n;i++){
for(int j=0;j<=m-a[i];j++){
dp[i+1][j+a[i]]+=dp[i][j];
}
}
dijkstraについて
私はBFSやDFSをまともに書けないのでdijkstraライブラリを貼ってごまかしています。C++なのでlogがついてもセーフ！をしています（良くない）。
この辺の記事を読むと良いかもしれません。
UnionFindについて
自分のライブラリを持っているんですがACLでいいと思います。あとはABC-D/Eくらいで連結成分の個数みたいなのが答えに関係してくる時は使う可能性が高いと思ってます。グリッド上のBFSで到達可能か判定するみたいなやつも最短経路を求める必要がなければUnionFindでサボれます（参考:ABC276-Eなど）。
その他いろいろ
A問題B問題みたいなのをいかにはやく書くかみたいなのは大事だと思っていて、タイピング速度が遅いのでなるべく簡潔に書けそうな実装を選ぶようにしています（XORとかはA問題で割と有用）。
さいごに
ARCで青落ちしないようにがんばります。少しでも同じような競技プログラマーの参考になれば幸いです。