社会人になって3年ぶりくらいにAtCoderをやってみて勉強しなおした知識まとめ。
3年前は水色だったけど、3年ぶりにABCに出たらパフォーマンス600くらいで泣いた。
新しいことを勉強したら、随時更新する。
水色に戻るまで
座標圧縮
数列の大小が必要だが差の大きさが必要ないとき使える。
数列Aを座標圧縮したいときは、数列Aを数列Bにコピーして、Bをソートして、mapを使って{num: index}みたいにして、数列Aの数字をindexに置換すれば良い。
参考記事: 座標圧縮 (座圧) – けんちょんの競プロ精進記録
Mod
数字が大きくなりすぎないように使う。四則演算と累乗はすぐにできるようにしておく必要がある。
参考記事
- 「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 – Qiita
- 【競プロライブラリ】mint(modint)で学ぶC++ – Qiita
- ac-library/document_ja/modint.md at master · atcoder/ac-library
ビット演算
2進数で全探索をするときなど。
ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜 – Qiita
二次元累積和
一次元の累積和がわかっていれば二次元も直感的だった。
問題を解くときの発想になかったので覚えておくと便利。
参考: 累積和を何も考えずに書けるようにする！ – Qiita
c++
vectorの参照渡し
関数にvectorを渡すとき参照渡しにしないと毎回deep copyになる(たぶん、少なくとも処理が遅くなってTLEになった)。
結論: &をつける。
// 良い例(vectorのshallow copy)
bool dfs(vector<string>& s, int n){
}// 悪い例(vectorのdeep copy)
bool dfs(vector<string> s, int n){
}
Comments