LoginSignup
2
2

More than 3 years have passed since last update.

@yamatonao

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

Last updated at Posted at 2020-04-21

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)

参考元

2
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
2