[C++]競技プログラミングで使える汎用処理まとめ ~Part1~

1.まえがき

Atcoder水色記念でなんか書けることないかと思い、
汎用的なアルゴリズムを纏めてみました。

問題を早く解くためには、解法を思いつくまでの時間が一番大きな要素ですが、
そのあとのコーディングにおいて、
すぐに使用できる汎用処理が手元にどれくらい用意できているか？
というのも重要だとおもいます

2. 本記事の概要

というわけで、今回は以下の汎用処理を紹介します。

• 二分探索
• 素因数分解
• mod 1000000007における各種演算処理(累乗、コンビネーション)

最近よく使うなあと思ったのを挙げただけなので、一貫性なくてすみません
下記にも置いてます
https://github.com/tks3210/Atcoder/tree/master/Tips

3. 汎用処理

3.1 二分探索

概要
　ソート済の配列に対して、条件を満たす要素の下限を算出する。計算量はO(logN)。
　　
コード
　神の英知であるめぐる式二分探索様をベースに、判定関数を引数から指定できるようにしました。

<制約事項>
　下記コード、やってることは二分探索なので、
　行列のある要素に対して指定した判定方法を満たすとき、
　それ以降の要素も判定方法を満たす必要があります。
　例えば、arr[3]の要素が指定した判定方法に対してTRUEを返す場合、
　arr[4],arr[5],...もTRUEを返すよう、配列と条件を指定する必要があります。

二分探索

/* 判定式を指定できる二分探索 */
/* input: arr:配列、callback:判定方法の関数ポインタ、 userQuery:判定に使用するための引数(省略可)*/
/* output: 条件を満たす要素の最小値(全て満たさなければ要素サイズを返す) */
/* 制約事項: 行列のある要素に対して判定方法callbackを満たすとき、それ以降の要素も判定方法を満たす必要がある。 */
template<class X> int binarySearch_mgr(vector<X> &arr, bool (*callback)(X, int), X userQuery = 0) {
    int ng = -1;
    int ok = (int)arr.size();
    while(abs(ok - ng) > 1){
        int mid = (ok + ng) / 2;
        if (callback(arr[mid], userQuery)){ ok = mid; } else { ng = mid; }
    }
    return ok;
}

/* 判定方法1 */
/* input: arrValue:行列の要素、user:任意に指定した引数*/
/* 行列要素arrValueが指定した値userより大きいとき真を返す */
template<class X> bool judge1(X arrValue, int user){
    return (arrValue >= (X)user);
}

/* 判定方法2 */
/* input: arrValue:行列の要素、user:任意に指定した引数*/
/* 行列要素arrValueが指定した値userの二乗がより大きいとき真を返す */
template<class X> bool judge2(X arrValue, int user){
    return (arrValue >= ((X)user*(X)user));
}


int main(){
    int a_data[] = {2, 4, 6, 8, 10, 86};
    vector<int> a(a_data, a_data + 6);
    for (int i = 0; i < 10; i++)
    {
        printf("[%d] => %d  ",i, binarySearch_mgr(a, judge1, i));
        printf("[%d] => %d  \n",i, binarySearch_mgr(a, judge2, i));
    }
}

実行結果

1. クエリより大きい行列要素の下限を返す。
2. クエリの二乗より大きい行列要素の下限を返す。

実行結果

[0] => 0  [0] => 0
[1] => 0  [1] => 0
[2] => 0  [2] => 1
[3] => 1  [3] => 4
[4] => 1  [4] => 5
[5] => 2  [5] => 5
[6] => 2  [6] => 5
[7] => 3  [7] => 6　← 満たさない場合は、行列のサイズ=6を返す。
[8] => 3  [8] => 6
[9] => 4  [9] => 6

3.1.補足（条件を満たすものが配列内に存在するか判定）

例えば、
「クエリ値が行列の要素に含まれない場合は-1を返す処理」を作りたい場合があると思います。
その場合、
下記のように「二分探索でクエリ値よりも大きい値の下限」を探し、
呼び出し側でその値がクエリ値を同じかをチェックすることで実現できます。

入力(該当部分のみ)

    for (int i = 0; i < 10; i++)
    {
        int ans = 0;
        if ((ans = a[binarySearch_mgr(a, judge1, i)]) != i){
            ans = -1;
        }
        printf("[%d] => %d  \n",i, ans);        
    }

出力

[0] => -1
[1] => -1
[2] => 2
[3] => -1
[4] => 4
[5] => -1
[6] => 6
[7] => -1
[8] => 8
[9] => -1

こんな感じで、
「配列内に条件を満たすものが存在するか否かを判定する」ような処理は、
最も満たす可能性が高い要素を抽出する条件で二分探索し、返ってきた要素をチェックすることで
実装できる（こともあります）

3.2 素因数分解

概要
　素因数分解する。計算量はざっくりO(N^(1/2))以下？（もっと早い方法はある？らしい。）
　分解したい整数と動的配列を引数にとり、整数の素因数を配列に格納する。

コード

最小の素数2から探索していき、割り切れる場合はその値で入力値を割っていく。
for文では複合数も探索対象となりますが、それより前の処理でその複合数を構成する素数での除算が終わっているので、複合数が動的配列に格納される事はないです。
（例えば、6で割り切れる数字の場合は、前段のi=2, i=3の時点で除算が行われるためi=6の時点で割り切れることがない。）

素因数分解

//素因数分解
template<class X> void factorization(X input, vector<X>& Pnumber){
    for(X i = 2; i*i <= input; i++)
    {
        if (input % i == 0){
            while (input % i == 0){
                input /= i;
                Pnumber.push_back(i);
            }
        }
    }
    if (input != 1) Pnumber.push_back(input);
}

int main(){
    long long N;
    vector<long long> Pnumber;
    cout << "Input>";
    cin >> N;

    factorization(N, Pnumber);
    cout << "Output>";
    for (auto i: Pnumber) cout << i << " ";
}

実行結果

Input>138338928000
Output>2 2 2 2 2 2 2 3 3 3 3 3 5 5 5 7 13 17 23

素数の最大値が大きいほど計算が遅くなり、最悪の場合N^(1/2)回if文が回る。。
long longの最大値の素数を入力すると、処理に3秒以上かかってしまいました。

3.3 mod 1000000007での各種演算処理

概要
mod 1000000007下での四則演算を行うクラス
mod下における、和と差と積は簡単ですが、割り算だけは逆元を求める必要があります。

逆元に関する説明は、下記記事の3.1節がめちゃめちゃ分かりやすかったです。
https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

コード

既にatcoder-liveで演算子オーバーロードされたクラスが下記リンクにて紹介されてましたので、
こちらでは、呼び出し側での使用例を記載しておきます
https://github.com/atcoder-live/library/blob/master/mint.cpp

mod演算

typedef struct mint
{
    /*上記git参照*/
} mint_t;

int main()
{
    int x = 2000000000;
    struct mint m(x);
    //和(2000000000 + 3000000000)
    cout << "+:   " << (m + 3000000000).x << endl; 
    //差(2000000000 - 1000000000)
    cout << "-:   " << (m - 1000000000).x << endl; 
    //積(2000000000 * 20)
    cout << "*:   " << (m * 20).x << endl; 
    //商(2000000000 / 20)
    cout << "/:   " << (m / 20).x << endl; 
    //累乗(2000000000^2000000000)
    cout << "a^b: " << (m.pow(2000000000)).x << endl;
    
    //Combination計算 n = 50000000000 m = 3
    ll N = 50000000000;
    ll M = 3;
    mint fac(1), ifac(1);
    for (int i = 0; i < M; i++){ fac *= N - i; } //nCmの分子を計算
    for (int i = 0; i < M; i++){ ifac *= i + 1; } //nCmの分母を計算
    ll ans = (fac * ifac.inv()).x; //分子に分母の逆元を積算
    cout << "nCm: " << ans << endl;
}

演算子オーバーロードされているため、
演算を行う場合はmintクラスのインスタンスを使って計算式を立てますが、
答えを出力するときは、.xでメンバ変数を参照する必要があります。

実行結果

+:   999999972
-:   1000000000
*:   999999727
/:   100000000
a^b: 497478644
nCm: 992792807

4.あとがき

調べれば調べるほど先駆者が出てきて投稿するかどうか悩んだ
次はDP、木構造あたりを纏めたいなあと思います。

5.偉大なる参考資料

mod 計算関係の記事、コード
「1000000007 で割ったあまり」の求め方を総特集！
Atcoder解説放送で使用されたmodライブラリ

二分探索
めぐる式二分探索法のススメ