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

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/