競技プログラミング自分用チートシート

# MOD界の割り算
mod p(p := primary number)での割算 a / b mod pは
a * (b^p-2 % p ) % pで求まる

```moddiv.cpp

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

tmp *= modinv(2, MOD);
tmp %= MOD;
```

# 最大公約数
3個の整数の最大公約数は、gcd(gcd(a,b),c)で求まる。同じ要領でn個の最大公約数

```gcd.cpp
int gcd(int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}
```

# Vector
*(vec.begin())は先頭要素を示すが、*(vec.end())は要素ではない。*(--vec.end())とすると末尾要素にアクセスできる
vectorに２つ以上要素をもたせたいときは、pair<> tuple<>が必須

```vector.cpp

// 隣接リスト表現
// 頂点n個
vector<vector<pair<ll, ll> > > Graph(n);

// 入れるとき
Graph[x].push_back( make_pair( a,b ) );
Graph[x].push_back( { a,b } ); // -std=c++17の指定が必要

// 取り出すとき
Graph[x][y].first;
Graph[x][y].second;
// or
typedef pair<ll, ll> P;
P p_tmp = Graph[x][y];
p_tmp.first;
p_tmp.second;
```

#multiset
insertは値を入れる。
eraseは値を入れると同じ値を全部削除してしまうので、かならずms.find(value)でイテレータを渡す。

#小数
* 誤差について
doubleでは誤差が発生し正しく計算できない場合が多い。対策は下記
    * long doubleを使って精度を上げる
    * stringで読み込んで小数点を除去して整数に変換する
    * 微小値を加算してから整数に変換する
    * round関数を使って四捨五入して誤差を飛ばす
* 出力を Cout にすると、AAAAe+YYYみたいな形式に勝手に変換されてしまうときがある。そのためprintf / もしくは出力形式を指定する必要がある。

```decimal.cpp
  cout << fixed << setprecision(15) << y << endl;
```

#二分探索
* lower_bound()/upper_bound()はどちらも指定値以上/より大きい。指定値以下のイテレータを返したかったら、upper_boundして--する。
* バグの温床でまともに一発で通すのは難しい。適当に数値を+1とかして帳尻合わせしようとしてもうまく行かない。きっちりかっきり机上デバッグしよう。
* もしくはめぐる式
* pairのvectorにしなくても、取得したイテレータ - begin()にするとindex求まる(vectorの場合)

```lower_bound.cpp
vector<pair<ll, ll > > xxx_total; // pair1つ目には値、pair2つ目にはindex
xxx_total.push_back({xxx_value, xxx_index});
auto xxx_itr = upper_bound(ALL(xxx_total), make_pair(xxx_total,INF)); //　--で後で一個後ろを参照したいので、const auto & itrにはしない
// auto xxx_itr = lower_bound(ALL(xxx_total), make_pair(xxx_total,-INF)); // lowerのときは-INFにしておく必要あり
// auto xxx_itr = lower_bound(ALL(xxx_total), make_pair(xxx_total,0)); // 0の部分で推論ミスってコンパイル通らないのでこれはだめ

// 指定値より大きい値のイテレータが帰ってきてるわけだから、うまく帳尻合わせする。
if(xxx_itr == end(xxx_total)){
    ans_index = xxx_total.size();
}else if(xxx_itr == begin(xxx_total)){
    ans_index = 0;
}else{
    ans_index = (*(--b_itr)).second;
    //ans_index = ll(b_itr - begin(xxx_total)); じつはこれでも
}
```
#その他
* __builtin_popcount(input) inputのonbit数を求める(templete)

#問題への取り組み方 
###数学系問題
* ノートを使用する
* 全探索で解けるか
* 妙に厳しい制約がないか。これを活かせないか
* 小さい数値/正の整数で試行する。周期性や単調増加/減少といった特徴が見つからないか
* 文章から数式を立式できないか。数式を変換できないか。式を変形して小数や√を消滅させることができないか(誤差に注意)
* 沢山の変数がうじゃうじゃ動くときは、一文字だけ動かしてみる。実は特定の範囲の値が自在に作れるかも  
* 二次元グルーピングで考えることができないか （ABC172D, ARC117B)
* DPは遷移式まで描いてから考えないと、必ずバグるので注意。特に、もらうか配るか常に考える。

###留意すべき観点
* 全探索するときの、forループの回し方に注意する。forループの回し方を変化させることで高速化できるかも  
結構forの回し方を考えずに実装してTLEする～に陥ってるため気をつける。
 * 入力で渡される値ではなく、出力する答えをiにして、iのときに答えの条件を満たしているかを確認する(ABC172C)
 * [1...n]を出力に要求されているとき、仕分けして最後に一気に出力すると早い場合がある(aising2020C)

# 参考元
* mod界の除算  
https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#4-%E7%B4%AF%E4%B9%97-an  
* 最大公約数  
https://note.com/kazusasan/n/n9ea759286ea3  
* 小数  
https://cpprefjp.github.io/reference/ios/defaultfloat.html  
https://drken1215.hatenablog.com/entry/2020/05/31/224300  
* 問題への取り組み方  
https://speakerdeck.com/furuya1223/the-view-of-green-difficulty-problems  
https://algo-logic.info/how-to-think-cp/