Kansu C++ Library — Full Dump for AI

add_file.md

add_file

all/AHC.md

AHC記録

手法

貪欲、ビムサ

盤面評価値が作れる

強い貪欲がある

解の一部を変化させると解が崩れるときに使う

(ビムサ)高速な盤面評価値が最強

貪欲系だとわかったら盤面評価値を考えておく

工夫

理論値が取れると信じてどうすればそれに近づけられるか考える

天才貪欲はシンプルなものが多い→最初から複雑に考察しようとしない

山登り→焼きなまし

解の一部を変化させても大丈夫な時に使う

高速な近傍、スコア計算が最強

序盤に勝手な判断で探索空間を狭めるのはダメ

工夫(焼き方がわからないとき)

ルール違反をペナルティ付きで許容する

自主制約をつける

巨大な近傍(部分破壊再構築)なら焼けるか？

原則としてスコア上限の高そうなものから考える

原則　焼きなまし＞ビムサ

モンテカルロ

インタラクティブの時

全体の学び

探索は強い

評価関数は基本的にゴミ

種類を増やしすぎると爆発する

アルゴリズムの高速化技術を制約から連想して応用すると高速化ができる

未来は大事

AHC 59

初期解の作成を再構築と同じ方法で行う

初期解を作成した後で、部分破壊から再構築をしていく

再構築を貪欲で行うことで高速にできる

それぞれの行動を数列にした順列を作成する

初期解の作成

順列の中に新しい操作を挿入していく

挿入位置を全探索し、もっとも良かったところに入れる

破壊再構築

長さ15程度の部分を選択し、その部分を削除、それぞれを貪欲で挿入し直す

AHC 58

貪欲の評価を行動をとった結果のスコアに対して行うのではなく、行動をとった結果のスコアの増加に対して行うといい

初期解の作成

貪欲で行動する

優先して強化するIDを全探索してみて一番良かったものを初期解として採用する

焼きなまし

普通の焼きなまし

AHC 57

距離が2000以下になったもの同士をくっつけていき最後にグループ数がちょうどよくなるようにくっつける

AHC 55

評価値をいい感じにした貪欲

それぞれのターンで使える武器のうちもっともダメージを与えられるものを使えばいいのだがそれを全体に占める割合にすることで他の武器では全然ダメージを与えられないような箱に対しても有効な攻撃ができる

ビジュアライザを見て上手くいっていない部分にどんな傾向があるのかを分析する

AHC 53

使うカードを大きいカードと小さいカードの二種類にわけて作る

フェーズ1で大きいカードを割り当て、フェーズ2で小さいカードを割り当てる

初期解を作成した後それぞれの山とフェーズをランダムで選択し、そのフェーズのカードの残りカードを半分全列挙によって探索をし、最適化をする

あまりカードの数が少ないことに注目すれば半分全列挙ができることがわかる

all/その他典型/RLE.md

ラングレス圧縮

string を入力

int char の　pair の vector でリターン

aaab -> { 3 , a } , { 1 , b }

vector<pair<int,char>> r(string s){
    vector<pair<int,char>> ans;
    for(int i = 0;i < s.size();i++){
        if(ans.size()==0 || ans[ans.size()-1].second != s[i]){
            ans.push_back({1,s[i]});
        }
        else{
            ans[ans.size()-1].first++;
        }
    } 
    return ans;
}

all/その他典型/Z.md

zアルゴリズム

文字列Sのそれぞれの位置についてそこから後ろの文字列とSとの最長共通接頭辞の長さをO(N)で計算できる

Z(S)でvector のリターン

単体比較

vector<int> z(string s){
    int n = s.size();
    vector<int> ans(n);
    int l=0,r=0;
    ans[0] = n;
    for(int i = 1;i < n;i++){
        if(i > r){
            int J = 0;
            int j = i;
            while(j < n && J < n && s[J] == s[j]){
                J++;
                j++;
            }
            ans[i] = J;
            r = j-1;
            l = i;
        }
        else{
            int j = min(i+ans[i-l],r);
            int J = j-i;
            while(j < n && J < n && s[J] == s[j]){
                J++;
                j++;
            }
            ans[i] = J;
            if(r < j-1){
                r = j-1;
                l = i;
            }            
        }
    }
    return ans;
}

複数比較

vector<int> z(string s,string t){
    // tのそれぞれについて計算される
    int S = s.size();
    s = s +"#"+t;
    int n = s.size();
    vector<int> ans(n);
    int l=0,r=0;
    ans[0] = n;
    for(int i = 1;i < n;i++){
        if(i > r){
            int J = 0;
            int j = i;
            while(j < n && J < n && s[J] == s[j]){
                J++;
                j++;
            }
            ans[i] = J;
            r = j-1;
            l = i;
        }
        else{
            int j = min(i+ans[i-l],r);
            int J = j-i;
            while(j < n && J < n && s[J] == s[j]){
                J++;
                j++;
            }
            ans[i] = J;
            if(r < j-1){
                r = j-1;
                l = i;
            }            
        }
    }
    vector<int> res;
    for(int i = S+1;i < ans.size();i++){
        res.push_back(ans[i]);
    }
    return res;
}

all/その他典型/index.md

その他典型 便利なやつ

all/その他典型/manacher.md

manacher 直径と半径

最大直径

“abcba”をこれに入れると”a%b%c%b%a”というダミー文字を間に挟んだ状態のものとして考えられる

それぞれの地点を中心とした回文の最大直径の大きさをO(N)で計算する

文字と文字の間も含めてそれぞれの場所を中心とした回文の最大の直径が計算できる

a | b | c | b | a 
1 0 1 0 5 0 1 0 1

aaaaの場合

a | a | a | a 
1 2 3 4 3 2 1 

vector<int> mana(string s){
    int n = s.size();
    string t = "%";
    rep(i,n){
        t += s[i];
        t += "%";
    }
    n = t.size();
    swap(s,t);
    vector<int> res(n,0);
    int y = -1;
    int x = -1;
    for(int i = 0;i < n;i++){
        int l = i,r = i;
        if(y >= i){
            int t = x*2 - i;
            r = min(y,i+res[t]-1);
            l -=  r-i;
        }
        while(l >= 0 && r < n && s[l]==s[r]){
            if(y < r){
                y = r;
                x = i;
            }
            l--;
            r++;
        }
        res[i] = r  - i;
    }
    rep(i,n)res[i]--;
    vector<int> ans;
    for(int i = 1;i < res.size()-1;i++)ans.push_back(res[i]);
    return ans;
}

最大半径

使い方は同じ

a | b | c | b | a 
1 0 1 0 3 0 1 0 1

aaaaの場合

a | a | a | a 
1 1 2 2 2 1 1

vector<int> mana(string s){
    int n = s.size();
    string t = "%";
    rep(i,n){
        t += s[i];
        t += "%";
    }
    n = t.size();
    swap(s,t);
    vector<int> res(n,0);
    int y = -1;
    int x = -1;
    for(int i = 0;i < n;i++){
        int l = i,r = i;
        if(y >= i){
            int t = x*2 - i;
            r = min(y,i+res[t]-1);
            l -=  r-i;
        }
        while(l >= 0 && r < n && s[l]==s[r]){
            if(y < r){
                y = r;
                x = i;
            }
            l--;
            r++;
        }
        res[i] = r  - i;
    }
    rep(i,n)res[i]--;
    vector<int> ans;
    for(int i = 1;i < res.size()-1;i++)ans.push_back((res[i]+1)/2);
    return ans;
}

特定の位置を起点とする回文の最大の長さを求める

manacherを使ってそれぞれの最大の長さの回文の始点と中心を求める

始点と中心をpairでを小さい順にソートする

答えを記録する配列を左から見てく

現在見てる位置よりも始点が左にある回文を全て確認してその中で中心が一番右にあるものがそこを始点とした最大の回文の中心となる

適切に計算すればO(NlogN)で計算ができる

all/その他典型/rmax.md

循環配列での長さwの区間の和の最大値

循環させる前の配列と長さWを入れる


    long long rmax(vector<int> v,long long w){
        int n = v.size();
        rep(i,n)v.push_back(v[i]);
        n *= 2;
        if(w >= n/2){
            long long ans = 0;
            rep(i,n/2)ans += v[i];
            return ans;
        }
        long long sum = 0;
        rep(i,w)sum += v[i];
        long long ans = sum;
        for(long long i = 0;i < n/2-1;i++){
            sum -= v[i];
            sum += v[i+w];
            ans = max(ans,sum);
        }
        return ans;
    }

all/その他典型/rmin.md

循環配列での長さwの区間の和の最小値

循環させる前の配列と長さWを入れる


    long long rmax(vector<int> v,long long w){
        int n = v.size();
        rep(i,n)v.push_back(v[i]);
        n *= 2;
        if(w >= n/2){
            long long ans = 0;
            rep(i,n/2)ans += v[i];
            return ans;
        }
        long long sum = 0;
        rep(i,w)sum += v[i];
        long long ans = sum;
        for(long long i = 0;i < n/2-1;i++){
            sum -= v[i];
            sum += v[i+w];
            ans = min(ans,sum);
        }
        return ans;
    }

all/その他典型/string部分一致.md

string部分一致確認


bool same(string& s,string& t,int x){
    // sのx文字目からがtと一致するならtrue
    int j = 0;
    for(int i = x;i < x+t.size();i++){
        if(i >= s.size())return false;
        if(j >= t.size())return false;
        if(s[i]!=t[j]){
            return false;
        }
        j++;
    }
    return true;
}

all/その他典型/ナップザック.md

ナップザック

int npz(vector<pair<int,int>> v,int w){
    //{重さ、価値}、重さ制限
    int n = v.size();
    vector<vector<int>> dp(n,vector<int>(w+1,-1));
    dp[0][0] = 0;
    if(v[0].first <= w){
        dp[0][v[0].first] = v[0].second;
    }
    for(int i = 0;i < n-1;i++){
        for(int j = 0;j <= w;j++){
            if(dp[i][j]==-1)continue;
            if(j+v[i+1].first <= w){
            dp[i+1][j+v[i+1].first] = max(dp[i+1][j+v[i+1].first],dp[i][j]+v[i+1].second);
            }
            dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
        }   
    }
    int ans = -1;
    for(int j = 0;j <= w;j++){
        ans = max(ans,dp[n-1][j]);
    }

    return ans;
}

all/その他典型/ナップザック復元.md

ナップザック復元

string npz_rev(vector<pair<long long,long long>> v,long long m){   
    // ( {重さ、価値} 、重さ制限 )

    // 必要 = A
    // どっちでも = B
    // いらない = C

    long long n = v.size();
    vector<vector<long long>> dp(n,vector<long long>(m+1,-INF));
    dp[0][0] = 0;
    if(v[0].first <= m){
        dp[0][v[0].first] = v[0].second;
    }
    for(long long i = 0;i < n-1;i++){
        for(long long j = 0;j <= m;j++){
            if(dp[i][j]==-INF)continue;
            if(j+v[i+1].first <= m){
            dp[i+1][j+v[i+1].first] = max(dp[i+1][j+v[i+1].first],dp[i][j]+v[i+1].second);
            }
            dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
        }   
    }
    long long maxvalue = 0;
    rep(i,m+1)maxvalue = max(maxvalue,dp[n-1][i]);
    pair<bool,bool> sss = {false,false};
    vector<pair<bool,bool>> ans(n,sss); 
    vector<vector<bool>> ok(n,vector<bool>(m+1,false));
    for(long long i = 0;i <= m;i++){
        if(dp[n-1][i]==maxvalue){
            ok[n-1][i] = true;
        }
    }
    vector<vector<long long>> cnt(n);
    for(long long i = n-1;i > 0;i--){
        for(long long j = 0;j <= m;j++){
            if(!ok[i][j])continue;
            if(dp[i-1][j]==dp[i][j]){
                ans[i].first = true;
                ok[i-1][j] = true;
            }
            if(j - v[i].first < 0)continue;
            if(dp[i-1][j-v[i].first] + v[i].second == dp[i][j]){
                ans[i].second = true;
                ok[i-1][j-v[i].first] = true;
            }
        }
    }
    if(ok[0][0]==true){
        ans[0].first = true;
    }
    if(v[0].first <= m &&  ok[0][v[0].first]){
        ans[0].second = true;
    }
    string ret;
    rep(i,n){
        if(ans[i].first && ans[i].second){
            ret += 'B';
        }
        else if(!ans[i].first && ans[i].second){
            ret += 'A';
        }
        else{
            ret += 'C';
        }
    }
    return ret;
}

all/その他典型/拡張ラングレス圧縮.md

ラングレス圧縮をstring以外の配列にも適用できるようになってるもの

全て ran(圧縮したい配列)　 でできる

vectorの圧縮






---

## all/その他典型/転倒数.md

# 転倒数

ten(v)に入れたら勝手に座標圧縮されて転倒数が帰ってくる

セグ木が一緒についてきてるのでセグ木を別で定義してる場合は気を付ける

転倒数 = 自分よりも左にあるのに自分よりも大きい要素の数の総和

配列の長さをNとした時 NlogN


```cpp
class st{
public:
    long long siz = 1;
    vector<long long> v;
    st (long long n){
        siz = 1;
        while(siz < n)siz *= 2;
        v.assign(2*siz,0);
    }
    void plus(long long i){
        i += siz;
        v[i]++;
        while(i > 1){
            i /= 2;
            v[i] = v[i*2]+v[i*2+1];
        }
    } 
    long long query(long long l,long long r){
        return query(l,r,1,0,siz-1);
    }
    private : 
    long long query(long long L,long long R,long long s,long long l,long long r){
        long long ans = 0;
        if(l >= L && r <= R){
            ans += v[s];
            return ans;
        }
        if(r < L || l > R)return 0;
        ans += query(L,R,s*2,l,(l+r)/2);
        ans += query(L,R,s*2+1,(l+r)/2+1,r);
        return ans;
    }
};

long long ten(vector<long long> v){
    long long n = v.size();
    vector<long long> sorted = v;
    sort(sorted.begin(),sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    st seg(sorted.size());
    long long ans = 0;
    for(long long i = 0;i < n;i++){
        long long pos = lower_bound(sorted.begin(),sorted.end(),v[i])-sorted.begin();
        ans += seg.query(pos+1,sorted.size()-1);
        seg.plus(pos);
    }
    return ans;
}

逆転倒数

自分よりも左にあって自分よりも小さい要素の数の総和を計算する

配列の長さをNとした時 NlogN

class st{
public:
    long long siz = 1;
    vector<long long> v;
    st (long long n){
        siz = 1;
        while(siz < n)siz *= 2;
        v.assign(2*siz,0);
    }
    void plus(long long i){
        i += siz;
        v[i]++;
        while(i > 1){
            i /= 2;
            v[i] = v[i*2]+v[i*2+1];
        }
    } 
    long long query(long long l,long long r){
        return query(l,r,1,0,siz-1);
    }
    private : 
    long long query(long long L,long long R,long long s,long long l,long long r){
        long long ans = 0;
        if(l >= L && r <= R){
            ans += v[s];
            return ans;
        }
        if(r < L || l > R)return 0;
        ans += query(L,R,s*2,l,(l+r)/2);
        ans += query(L,R,s*2+1,(l+r)/2+1,r);
        return ans;
    }
};
long long ten(vector<long long> v){
    long long n = v.size();
    vector<long long> sorted = v;
    sort(sorted.begin(),sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    st seg(sorted.size());
    long long ans = 0;
    for(long long i = 0;i < n;i++){
        long long pos = lower_bound(sorted.begin(),sorted.end(),v[i])-sorted.begin();
        ans += seg.query(0,pos-1);
        seg.plus(pos);
    }
    return ans;
}

all/グラフ/index.md

グラフアルゴリズム一覧

all/グラフ/グラフ法則.md

all/グラフ/グリッド上の最短経路.md

グリッド上の最短経路を求める

= 壁

. = 道

のグリッドでi,jからx,yまでの最短距離を計算する

int way(vector<vector<char>>& v ,int I,int J,int x,int y){
    queue<pair<int,int>> q;
    q.push({I,J});
    vector<vector<int>> ans(v.size(),vector<int>(v[0].size(),-1));
    while(q.size()!=0){
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        if(v[i-1][j]=='.' && ans[i-1][j]==-1){
            ans[i-1][j] = ans[i][j]+1;
            q.push({i-1,j});
        }
        if(v[i+1][j]=='.' && ans[i+1][j]==-1){
            ans[i+1][j] = ans[i][j]+1;
            q.push({i+1,j});
        }
        if(v[i][j-1]=='.' && ans[i][j-1]==-1){
            ans[i][j-1] = ans[i][j]+1;
            q.push({i,j-1});
        }
        if(v[i][j+1]=='.' && ans[i][j+1]==-1){
            ans[i][j+1] = ans[i][j]+1;
            q.push({i,j+1});
        }        
    }
    return {ans[x][y]};
}

all/グラフ/ダイクストラ.md

ダイクストラ

vector<vector<pair<int,int»>の形のグラフを投入

v[i]にあるvector<pair<int,int»をpとしたときpにはiからの{行き先、距離}を記録する

ds(グラフ,スタート地点)

スタート視点からの距離が記録されたvectorが帰ってくる

負の重みを持つ辺を入れてはいけない



vector<long long> ds(vector<vector<pair<long long,long long>>>& v,long long str){
    long long inf = 1e9;
    vector<long long> ans(v.size(),inf);
    ans[str] = 0;
    priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>> q;
    q.push({0,str});
    while(q.size()!=0){
        long long cos = q.top().first;
        long long pos = q.top().second;
        q.pop();
        if(cos > ans[pos])continue;
        for(pair<long long,long long> i : v[pos]){
            if(ans[i.first] > cos + i.second){
                ans[i.first] = cos + i.second;
                q.push({cos+i.second,i.first});
            }
        }
    }
    return ans;
}

all/グラフ/トポロジカルソート.md

トポロジカルソート

vviのグラフを入れるとviの順番が返ってくる

vector<int> tpr(vector<vector<int>> v){
    int n = v.size();
    vector<int>ans;
    vector<int> cnt(n,0);
    for(int i = 0;i < n;i++){
        for(int j : v[i]){
            cnt[j]++;
        }
    }
    queue<int> q;
    for(int i = 0;i < n;i++){
        if(cnt[i]==0)q.push(i);
    }
    while(q.size()!=0){
        int pos = q.front();
        ans.push_back(pos);
        q.pop();
        for(int i : v[pos]){
            cnt[i]--;
            if(cnt[i]==0){
                q.push(i);
            }
        }
    }
    return ans;
}

all/グラフ/フローまとめ.md

フローのあれこれ

all/グラフ/ワーシャルフロイド.md

ワーシャルフロイド

vvpの形のグラフを入れる

wf(vvp) でvviに変換されて返ってくる


vector<vector<int>> wf(vector<vector<pair<int,int>>> v){
    int n = v.size();
    vector<vector<int>> dis(n);
    for(int i = 0;i < n;i++){
        vector<int> ans(n,inf);
        ans[i] = 0;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
        q.push({0,i});
        while(q.size()!=0){
            int cos = q.top().first;
            int pos = q.top().second;
            q.pop();
            if(ans[pos] < cos)continue;
            for(pair<int,int> p : v[pos]){
                if(ans[p.first] > ans[pos]+p.second){
                    ans[p.first] = ans[pos]+p.second;
                    q.push({ans[pos]+p.second,p.first});
                }
            }
        }
        dis[i] = ans;
    }
    return dis;
}

all/グラフ/二部マッチング.md

二部マッチング

AIに書かせました また今度ちゃんと書きます

計算量 E √ V 
class bipartite_matching{
public:
    int nL,nR;
    vector<vector<int>> g;
    vector<int> dist;
    vector<int> matchL,matchR;

    bipartite_matching(int L,int R){
        nL = L;
        nR = R;
        g.resize(nL);
        matchL.assign(nL,-1);
        matchR.assign(nR,-1);
        dist.resize(nL);
    }

    void add_edge(int l,int r){
        // l : 0..nL-1, r : 0..nR-1
        g[l].push_back(r);
    }

    bool bfs(){
        queue<int> q;
        for(int i = 0;i < nL;i++){
            if(matchL[i] == -1){
                dist[i] = 0;
                q.push(i);
            }
            else{
                dist[i] = -1;
            }
        }

        bool reachable = false;

        while(!q.empty()){
            int v = q.front();
            q.pop();
            for(int to : g[v]){
                int u = matchR[to];
                if(u >= 0){
                    if(dist[u] < 0){
                        dist[u] = dist[v] + 1;
                        q.push(u);
                    }
                }
                else{
                    reachable = true;
                }
            }
        }
        return reachable;
    }

    bool dfs(int v){
        for(int to : g[v]){
            int u = matchR[to];
            if(u < 0 || (u >= 0 && dist[u] == dist[v] + 1 && dfs(u))){
                matchL[v] = to;
                matchR[to] = v;
                return true;
            }
        }
        dist[v] = -1;
        return false;
    }

    int max_matching(){
        int res = 0;
        while(bfs()){
            for(int i = 0;i < nL;i++){
                if(matchL[i] == -1){
                    if(dfs(i)){
                        res++;
                    }
                }
            }
        }
        return res;
    }
};

all/グラフ/強連結成分分解.md

強連結成分分解

強連結成分それぞれをvectorにまとめたvviでreturnが来る

scc( 頂点数　、　vviの形のグラフ　）　でできる

vector<vector<int>> scc(int n,const vector<vector<int>>& v){
    vector<vector<int>> vv(n);
    for(int i = 0;i < n;i++){
        for(int j = 0;j < v[i].size();j++){
            vv[v[i][j]].push_back(i);
        }
    }
    vector<int> res;
    vector<bool> visited(n,false);
    function<void(int)> f = [&](int pos){
        visited[pos] = true;
        for(int i : v[pos]){
            if(!visited[i])f(i);
        }
        res.push_back(pos);
    };
    for(int i = 0;i < n;i++){
        if(!visited[i]){
            f(i);
        }
    }
    vector<vector<int>> ans;
    visited.assign(n,false);
    for(int i = res.size()-1; i >= 0;i--){
        if(visited[res[i]])continue;
        vector<int> p = {res[i]};
        function<void(int)> d = [&](int pos){
            visited[pos] = true;
            for(int i : vv[pos]){
                if(visited[i])continue;
                p.push_back(i);
                d(i);
            }
        };
        d(res[i]);
        ans.push_back(p);
    }
    return ans;
}

all/グラフ/最大フロー.md

最大フロー

add(u,v,f) u ~ v にcapがfの辺を追加して

flow(s,t) で結果が出てくる

class din{

    struct edge{
        int to;
        int cap;
        int rev;
    };

    public : 
    int n;
    vector<vector<edge>> g;
    vector<int> level;
    vector<int> ite;

    din(int x){
        n = x;
        g.resize(n);
        level.resize(n);
        ite.resize(n);
    }

    void add(int from,int to,int cap){
        g[from].push_back(edge{to,cap,(int)g[to].size()});
        g[to].push_back(edge{from,0,(int)g[from].size()-1});
    }

    bool bfs(int s,int t){
        level.assign(n,-1);
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while(q.size()!=0){
            int pos = q.front();
            q.pop();
            for(const edge& e : g[pos]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[pos]+1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }
    int dfs(int v,int t,int f){
        if(v==t)return f;
        for(int &i = ite[v];i < (int)g[v].size();i++){
            edge& e = g[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                int d = dfs(e.to,t,min(f,e.cap));
                if(d > 0){
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int flow(int s,int t){
        int ans = 0;
        while(1){
            if(!bfs(s,t))break;
            ite.assign(n,0);
            int f = dfs(s,t,INF);
            while(1){
                if(f>0){
                    ans += f;
                    f = dfs(s,t,INF);
                }
                else{
                    break;
                }
            }
            
        }
        return ans;
    }

};

辺を復元したい


class din{

    struct edge{
        int to;
        int cap;
        int rev;
    };

    public : 
    int n;
    vector<vector<edge>> g;
    vector<int> level;
    vector<int> ite;

    din(int x){
        n = x;
        g.resize(n);
        level.resize(n);
        ite.resize(n);
    }

    void add(int from,int to,int cap){
        g[from].push_back(edge{to,cap,(int)g[to].size()});
        g[to].push_back(edge{from,0,(int)g[from].size()-1});
    }

    bool bfs(int s,int t){
        level.assign(n,-1);
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while(q.size()!=0){
            int pos = q.front();
            q.pop();
            for(const edge& e : g[pos]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[pos]+1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }
    int dfs(int v,int t,int f){
        if(v==t)return f;
        for(int &i = ite[v];i < (int)g[v].size();i++){
            edge& e = g[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                int d = dfs(e.to,t,min(f,e.cap));
                if(d > 0){
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int flow(int s,int t,vector<pair<int,int>>& res){
        int ans = 0;
        while(1){
            if(!bfs(s,t))break;
            ite.assign(n,0);
            int f = dfs(s,t,INF);
            while(1){
                if(f>0){
                    ans += f;
                    f = dfs(s,t,INF);
                }
                else{
                    break;
                }
            }            
        }
        rep(i,n){
            for(edge& e : g[i]){
                if(e.to==s || e.to==t)continue;
                if(e.cap==0){
                    res.push_back({i,e.to});
                }
            }
        }
        return ans;
    }
    int flow(int s,int t){
        int ans = 0;
        while(1){
            if(!bfs(s,t))break;
            ite.assign(n,0);
            int f = dfs(s,t,INF);
            while(1){
                if(f>0){
                    ans += f;
                    f = dfs(s,t,INF);
                }
                else{
                    break;
                }
            }            
        }
        return ans;
    }
};

all/グラフ/最小全域木.md

無向グラフの最小全域木

vector<vector<pair<int,int»> の状態のグラフを入れる

最小全域木のコストが返ってくる

非連結の場合は-1が返ってくる


long long cost(vector<vector<pair<long long,long long>>>& v){
    long long n = v.size();
    long long ans = 0;
    dsu d(n);
    priority_queue<pair<long long,pair<long long,long long>>,vector<pair<long long,pair<long long,long long>>>,greater<pair<long long,pair<long long,long long>>>> q;
    rep(i,n)for(pair<long long,long long> p : v[i]){
        if(p.first > i){
            q.push({p.second,{i,p.first}});
        }
    }
    while(q.size()!=0){
        long long w = q.top().first;
        long long x = q.top().second.first;
        long long y = q.top().second.second;
        q.pop();
        if(!d.same(x,y)){
            ans += w;
            d.merge(x,y);
        }
    }
    if(d.size(0)!=n)return -1;
    return ans;
}

最小全域木の内容が欲しい場合


vector<pair<long long,long long>>  cost(vector<vector<pair<long long,long long>>>& v){
    long long n = v.size();
    vector<pair<long long,long long>> ans;
    dsu d(n);
    priority_queue<pair<long long,pair<long long,long long>>,vector<pair<long long,pair<long long,long long>>>,greater<pair<long long,pair<long long,long long>>>> q;
    rep(i,n)for(pair<long long,long long> p : v[i]){
        if(p.first > i){
            q.push({p.second,{i,p.first}});
        }
    }
    while(q.size()!=0){
        long long w = q.top().first;
        long long x = q.top().second.first;
        long long y = q.top().second.second;
        q.pop();
        if(!d.same(x,y)){
            d.merge(x,y);
            ans.push_back({x,y});
        }
    }
    if(d.size(0)!=n)return {{-1,-1}};
    return ans;
}

all/グラフ/木直径.md

木の直径を求める

cho(vvi) vviのグラフを入れる

木の直径が返ってくる

int cho(vector<vector<int>>& v){
    int n = v.size();
    vector<int> go(n,-1);
    queue<int> q;
    q.push(0);
    go[0] = 0;
    while(q.size()!=0){
        int pos = q.front();
        q.pop();
        for(int i : v[pos]){
            if(go[i] == -1){
                go[i] = go[pos]+1;
                q.push(i);
            }
        }
    }
    int st = max_element(go.begin(),go.end())-go.begin();
    q.push(st);
    go.assign(n,-1);
    go[st] = 0;
    while(q.size()!=0){
        int pos = q.front();
        q.pop();
        for(int i : v[pos]){
            if(go[i] == -1){
                go[i] = go[pos]+1;
                q.push(i);
            }
        }
    }
    return *max_element(go.begin(),go.end());
}

変に重みがついてる場合

int cho(vector<vector<pair<int,int>>>& v){
    int n = v.size();
    vector<int> go(n,-1);
    queue<int> q;
    q.push(0);
    go[0] = 0;
    while(q.size()!=0){
        int pos = q.front();
        q.pop();
        for(pair<int,int> p : v[pos]){
            if(go[p.first] == -1){
                go[p.first] = go[pos]+p.second;
                q.push(p.first);
            }
        }
    }
    int st = max_element(go.begin(),go.end())-go.begin();
    q.push(st);
    go.assign(n,-1);
    go[st] = 0;
    while(q.size()!=0){
        int pos = q.front();
        q.pop();
        for(pair<int,int> i : v[pos]){
            if(go[i.first] == -1){
                go[i.first] = go[pos]+i.second;
                q.push(i.first);
            }
        }
    }
    return *max_element(go.begin(),go.end());
}

直径になるペアが知りたい場合


pair<int,int> cho(vector<vector<int>>& v){
    int n = v.size();
    vector<int> go(n,-1);
    queue<int> q;
    q.push(0);
    go[0] = 0;
    while(q.size()!=0){
        int pos = q.front();
        q.pop();
        for(int i : v[pos]){
            if(go[i] == -1){
                go[i] = go[pos]+1;
                q.push(i);
            }
        }
    }
    int st = max_element(go.begin(),go.end())-go.begin();
    q.push(st);
    go.assign(n,-1);
    go[st] = 0;
    while(q.size()!=0){
        int pos = q.front();
        q.pop();
        for(int i : v[pos]){
            if(go[i] == -1){
                go[i] = go[pos]+1;
                q.push(i);
            }
        }
    }
    return {st,max_element(go.begin(),go.end()) - go.begin()};
}

all/二分探索/index.md

二分探索

all/二分探索/二分探索.md

二分探索

all/二分探索/二分探索用vector.md

二分探索用vector

使い方は普通のvectorと同じ

lb = lower_bound

up = upperbound

ika = 以下

mim = 未満

結果がイテレータではなく添字で帰ってくる

end() に相当するリターンは-1

X ~ Y　の間にある個数を数えたいときは ub(Y) - lb(X)


class bs{
    public : 
    vector<long long> v;
    bs(long long n,long long x){
        v.assign(n,x);
        return;
    }
    void sort(){
        std::sort(v.begin(),v.end());
    }
    long long& at(long long pos){
        return v[pos];
    }
    long long& operator[](long long pos){
        return v[pos];
    }
    const long long& operator[](long long pos) const{
        return v[pos];
    }
    void push_back(long long x){
        v.push_back(x);
    }
    void pop_back(){
        v.pop_back();
    }
    long long lb(long long x){
        auto it = lower_bound(v.begin(),v.end(),x);
        if(it == v.end()){
            return -1;
        }
        else{
            return it - v.begin();
        }
    }
    long long ub(long long x){
        auto it = upper_bound(v.begin(),v.end(),x);
        if(it == v.end()){
            return -1;
        }
        else{
            return it - v.begin();
        }
    }
    long long mim(long long x){
        auto it = lower_bound(v.begin(),v.end(),x);
        if(it == v.begin()){
            return -1;
        }
        else{
            --it;
            return it - v.begin();
        }
    }
    long long ika(long long x){
        auto it = upper_bound(v.begin(),v.end(),x);
        if(it == v.begin()){
            return -1;
        }
        else{
            --it;
            return it - v.begin();
        }       
    }
    long long cnt_ika(long long x){
        return ika(x)+1;
    }
    long long cnt_mim(long long x){
        return mim(x)+1;
    }
    long long cnt_lb(long long x){
        if(lb(x) == -1){
            return 0;
        }
        return v.size() - lb(x);
    }
    long long cnt_ub(long long x){
        if(ub(x)==-1){
            return 0;
        }
        return v.size() - ub(x);
    }
};

all/二分探索/答えが広義短調増加になる問題の二分探索.md

答えが広義短調増加となる問題での特定の値の範囲を求める二分探索

int test(mid) でmid の時の値を返す関数を作っておく必要がある

bs(k) = 答えがkとなる範囲を{L,R}のpairで返す


pair<int,int> bs(int k){
    int big,small;
    int l = 0;
    int r = INF;
    while(l+1 < r){    // find big
        int mid = (l+r)/2;
        int res = test(mid);
        if(res > k) r = mid;
        else l = mid;
    }
    big = l;
    l = 0;
    r = INF;
    while(l+1 < r){    // find small
        int mid = (l+r)/2;
        int res = test(mid);
        if(res >= k)r = mid;
        else l = mid;
    }    
    small = r;
    if(small > big) return {-1, -1};
    return {small,big};
}

all/二分探索/答えが短調非減少になる問題の二分探索.md

短調非増加の答えでの値Kの範囲

int test(mid) の関数をあらかじめ作っておく必要がある

bs(k) = 答えがkになる範囲の{L,R}をpairで返す


pair<int,int> bs(int k){

    int big,small;
    int l = 0;
    int r = INF;
    while(l+1 < r){    // find big
        int mid = (l+r)/2;
        int res = test(mid);
        if(res >= k){
            l = mid;
        }
        else{
            r = mid;
        }
    }
    big = l;
    l = 0;
    r = INF;
    while(l+1 < r){    // find small
        int mid = (l+r)/2;
        int res = test(mid);
        if(res > k){
            l = mid;
        }
        else{
            r = mid;
        }
    }    
    small = r;
    return {small,big};
}

all/二分探索/答えでlower_bound.md

答えでlower_bound

intを返すtest()を作っておく必要がある


int bs(int x){
    // xについてlower_bound
    int l = -1;
    int r = INF;
    while(l+1 < r){
        int mid = (l+r)/2;
        if(test(mid) >= x)r = mid;
        else l = mid;
    }
    return r;
}

all/二分探索/答えでupper_bound.md

答えでupper_bound

intを返すtest()を作っておく必要がある


int bs(int x){
    // xについてupper_bound
    int l = -1;
    int r = INF;
    while(l+1 < r){
        int mid = (l+r)/2;
        if(test(mid) > x)r = mid;
        else l = mid;
    }
    return r;
}

all/二分探索/答えで二分探索.md

答えで二分探索

boolを返すtestという関数にmidを入れれば使える状態にしておく必要がある

答えの最小化

true true true false false

このtrueとなる時の値を返す


int bs_min(){
    long long l = 0;
    long long r = 1e18;
    while (r - l > 1) {
        long long mid = (l + r) / 2;
        if (test(mid)) {
            r = mid;     
        } else {
            l = mid;     
        }
    }
    return r;
}

all/数学/N以下の約数の個数の総和.md

N以下の約数の個数の総和を求める

cnt(N,mod) N以下の約数の個数の総和

答えがデカくなることがあるのでmodであまりをとった結果が返ってくる

計算量O(√N)

long long cnt(long long n,long long mod){
    long long ans = 0;
    long long y = n;
    long long hidari = 0;
    while(y!=0){
        long long migi = n/y;
        ans += ((migi - hidari)%mod)*(y%mod);
        ans %= mod;
        y = n/(migi+1);
        hidari = migi;
    }
    return ans;
}

all/数学/N進数変換.md

N進数変換

10進数の時はintを使い他のときはstringを使っている

10 -> N

f(n,N)　で任意の10進数n をN進数に変換できる


string f(int n,int N){
    string ans = "";
    while (n) {
        ans.push_back('0' + n % N);
        n /= N;
    }
    reverse(ans.begin(),ans.end());
    return ans;
}

N -> 10

f(s,n) で任意のn進数(n < 10)を10進数に変換できる

int f(string s, int n){
    int v = 0;
    for(char c : s){
        v = v * N + (c - '0');
    }
    return v;
}

X -> y



// 先頭の 0 を削除
void trim(vector<int>& a){
    while(a.size() > 1 && a[0] == 0) a.erase(a.begin());
}

// a（x進数）を y で割る
// 商を a に格納し、余りを返す
int div_mod(vector<int>& a, int x, int y){
    vector<int> q;
    int cur = 0;
    for(int d : a){
        cur = cur * x + d;
        q.push_back(cur / y);
        cur %= y;
    }
    a = q;
    trim(a);
    return cur;
}

// x進数(string) → y進数(string)
string f(string s, int x, int y){
    vector<int> a;
    for(char c : s) a.push_back(c - '0');
    trim(a);

    if(a.size() == 1 && a[0] == 0) return "0";

    string res;
    while(!(a.size() == 1 && a[0] == 0)){
        int r = div_mod(a, x, y);
        res.push_back(char('0' + r));
    }
    reverse(res.begin(), res.end());
    return res;
}

all/数学/index.md

数学

all/数学/nCr.md

nCrを計算する

rを固定してnをr+xにしたときのそれぞれのxに対するnCrを計算しておく

xrCr(xの最大値,rの値)　でACLのmodntで答えが返ってくる

計算量はO(N)

vector<modint998244353> xrCr(int x_max,int r){
    vector<modint998244353> res(x_max+1);
    res[0] = 1;
    for(int i = 1;i <= x_max;i++){
        res[i] = res[i-1] * (r+i) / (i);
    }
    return res;
}

all/数学/エラトステネスの篩.md

エラトステネスの篩

p(n) = vectorの中にp以下の素数を列挙してリターンする

計算量 NloglogN

vector<int> p(int n) {
    vector<bool> ok(n+1,1);
    ok[0] = ok[1] = 0;
    for(int i = 2;i*i < n+1;i++){
        if(ok[i]){
            for(int j = i*i;j < n+1;j += i){
                ok[j] = 0;
            }
        }
    }
    vector<int> ans;
    rep(i,n+1){
        if(ok[i]){
            ans.push_back(i);
        }
    }
    return ans;
}

all/数学/ダブリング.md

ダブリング

dub(vector) で宣言する

引数のvectorはそれぞれの場所について次の日に行く場所を記録

query(x,y)で今xにいる時y日後の場所がわかる


class dub{
    public: 
    vector<vector<int>> d;
    int n;
    dub(vector<int>& a){

        // 今の場所 i 　
        // 次の日 a[i]　
        // のvectorを入れる

        n = a.size();
        d.assign(n,vector<int>(64));
        rep(i,n){
            d[i][0] = a[i];
        }
        for(int j = 1;j < 64;j++){
            for(int i = 0;i < n;i++){
                d[i][j] = d[d[i][j-1]][j-1];
            }
        }        
    }
    int query(int x,int y){
        //  今xにいる時y日後にいるところ
        bitset<64> b(y);
        int now = x;
        rep(i,64){
            if(b.test(i)){
                now = d[now][i];
            }
        }   
        return now;     
    }
};

all/数学/中央値.md

中央値

chu(v) でvの中央値が求められる

中央値は小数になることもあることに注意


template<typename T> 
double chu(vector<T> v){
    int n = v.size();
    sort(v.begin(),v.end());
    if(n%2==0){
        return (double)(v[n/2-1]+v[n/2])/(double)2;
    }
    else{
        return (double)v[n/2];
    }
}

all/数学/二次方程式.md

二次方程式

二次方程式の正数解を探す

答えが整数にならない場合は-1が返ってくる

rの値はいい感じに調節してください

long long f(long long a, long long b, long long c) {
    // ax^2 + bx + c = 0の解
    long long l = 0, r = 600000001; // ありうる答えの最大値
    while (r - l > 1) {
        long long mid = (l + r) / 2;
        if (a * mid * mid + b * mid + c <= 0)l = mid;
        else r = mid;
    }
    if (a * l * l + b * l + c == 0)return l;
    return -1;
}

all/数学/分数.md

分数

分数を扱える構造体

+ - * / ができる

あまり大きくしすぎると壊れる

比較演算とsortがそのまま使える

初期化

ft x = {3,4} // ４分の３

class ft{
public:
    long long si, bo; // si/bo

    ft(long long s=0, long long b=1){
        si = s; bo = b;
        normalize();
    }

    void normalize(){
        if(bo < 0) si = -si, bo = -bo;
        long long g = gcd(llabs(si), llabs(bo));
        si /= g;
        bo /= g;
    }

    // 加算
    ft operator+(const ft& x) const {
        long long g = gcd(bo, x.bo);
        __int128 nb = (__int128)bo / g * x.bo;
        __int128 ns =
            (__int128)si * (x.bo / g)
          + (__int128)x.si * (bo / g);
        return ft((long long)ns, (long long)nb);
    }

    // 減算
    ft operator-(const ft& x) const {
        long long g = gcd(bo, x.bo);
        __int128 nb = (__int128)bo / g * x.bo;
        __int128 ns =
            (__int128)si * (x.bo / g)
          - (__int128)x.si * (bo / g);
        return ft((long long)ns, (long long)nb);
    }

    // 乗算
    ft operator*(const ft& x) const {
        long long g1 = gcd(llabs(si), llabs(x.bo));
        long long g2 = gcd(llabs(x.si), llabs(bo));
        __int128 ns = (__int128)(si/g1) * (x.si/g2);
        __int128 nb = (__int128)(bo/g2) * (x.bo/g1);
        return ft((long long)ns, (long long)nb);
    }

    // 除算
    ft operator/(const ft& x) const {
        assert(x.si != 0);
        long long g1 = gcd(llabs(si), llabs(x.si));
        long long g2 = gcd(llabs(x.bo), llabs(bo));
        __int128 ns = (__int128)(si/g1) * (x.bo/g2);
        __int128 nb = (__int128)(bo/g2) * (x.si/g1);
        return ft((long long)ns, (long long)nb);
    }

    // 比較
    bool operator<(const ft& x) const {
        return (__int128)si * x.bo < (__int128)x.si * bo;
    }
    bool operator==(const ft& x) const {
        return si == x.si && bo == x.bo;
    }
};

all/数学/区間篩.md

区間篩

e(L,R)でLからRまでを全て素因数分解する

計算量はNloglogNとかになるらしい

vector<vector<pair<long long,long long>>> e(long long l,long long r){
    vector<bool> b(sqrtl(r)+3,true);
    vector<long long> so;
    for(long long i = 2;i < b.size();i++){
        if(b[i])so.push_back(i);
        for(long long j = i+i;j < b.size();j+=i){
            b[j] = false;
        }
    }
    vector<long long> v;
    for(long long i = l;i <= r;i++)v.push_back(i);
    vector<vector<pair<long long,long long>>> ans(v.size());
    for(long long i : so){
        for(long long j = max(i,((l+i-1ll)/i))*i;j <= r;j+=i){
            int J = j-l;
            long long cnt = 0;
            while(v[J]%i==0){
                v[J]/=i;
                cnt++;
            }
            if(cnt!=0)ans[J].push_back({i,cnt});
        }
    }
    for(long long i = 0;i < v.size();i++){
        if(v[i]!=1)ans[i].push_back({v[i],1});
    }
    return ans;
}

区間篩を用いた素因数の種類数のカウント

e(L,R)でL〜Rまでの数のやk数の個数を列挙する

vector<long long> e(long long l,long long r){
    vector<bool> b(sqrtl(r)+3,true);
    vector<long long> so;
    for(long long i = 2;i < b.size();i++){
        if(b[i])so.push_back(i);
        for(long long j = i+i;j < b.size();j+=i){
            b[j] = false;
        }
    }
    vector<long long> v;
    for(long long i = l;i <= r;i++)v.push_back(i);
    vector<long long> ans(v.size());
    for(long long i : so){
        for(long long j = max(i,((l+i-1ll)/i))*i;j <= r;j+=i){
            int J = j-l;
            long long cnt = 0;
            while(v[J]%i==0){
                v[J]/=i;
                cnt++;
            }
            if(cnt!=0)ans[J]++;
        }
    }
    for(long long i = 0;i < v.size();i++){
        if(v[i]!=1)ans[i]++;
    }
    return ans;
}

all/数学/座標圧縮.md

座標圧縮

結果を入れるmap、逆の復元用のvector、圧縮したいvector　を入れる

mapに圧縮前の座礁を入れると圧縮後の座標が帰ってくる

vectorに圧縮後の座標を入れると圧縮前の座標が帰ってくる

void ash(map<int,int>& m,vector<int>& g,vector<int> v){
    int n = v.size();
    m.clear();
    sort(v.begin(),v.end());
    int j = 0;
    for(int i = 0;i < n;i++){
        if(m.count(v[i]))continue;
        m[v[i]] = j;
        while ((int)g.size() <= j) g.push_back(0);
        g[j] = v[i];
        j++;
    }
    return ;
}

all/数学/数字桁数.md

数字桁数

ket(x)でxの桁数が返ってくる


int ket(int n){
    int ans = 0;
    while(n != 0){
        ans++;
        n /= 10;
    }
    return ans;
}

all/数学/最長増加部分列.md

最長増加部分列

lis_sizeで最長部分増加列の長さ

los_posでそれぞれの位置までの最長増加部分列の長さが記録されたvectorが帰っってくる


    int lis_size(vector<int> v){
        vector<int> dp;
        int n = v.size();
        for(int i : v){                
            auto it = lower_bound(dp.begin(),dp.end(),i);
            if(it == dp.end())dp.push_back(i);
            else *it = i;
        }
        return dp.size();
    }
    vector<int> lis_pos(vector<int> v){
        vector<int> dp;
        int n = v.size();
        vector<int> ans(n);
        for(int j = 0;j < n;j++){
            int i = v[j];
            auto it = lower_bound(dp.begin(),dp.end(),i);
            if(it == dp.end()){
                dp.push_back(i);
                ans[j] = dp.size();
            }
            else{
                *it = i;
                ans[j] = (it - dp.begin())+1;
            }
        }
        return ans;
    }

all/数学/素因数分解pi.md

素因数分解　pair int,int

vector<pair<int,int>>  p(int n){
    vector<pair<int,int>> ans;
    int x = n;
    int k = 0;
    while(x % 2 == 0){
        k++;
        x /= 2;
    }
    if(k != 0){
        ans.push_back({2,k});
    }
    for(int i = 3;i * i <= n;i+=2){
        int cnt = 0;
        while(x % i == 0){
            cnt++;
            x /= i;
        }
        if(cnt != 0){
            ans.push_back({i,cnt});
        }
        if(x == 1){
            break;
        }
    }
    if(x!=1)ans.push_back({x,1});
    return ans;
};

all/数学/素因数分解vi.md

素因数分解 vector int


vector<int> p(int n){
    vector<int> ans;
    int x = n;
    while(x % 2 == 0){
        x /= 2;
        ans.push_back(2);
    }
    for(int i = 3;i * i <= n;i+=2){
        while(x % i == 0){
            x /= i;
            ans.push_back(i);
        }
        if(x == 1){
            break;
        }
    }
    if(x!=1)ans.push_back(x);
    return ans;
};

all/構造体/RMaxQ.md

RMaxQ

segmenttree 名前(サイズ)　で定義

名前.update( i , x ) で i 番目の要素を x に変更

名前.query( l , r ) で l から r の範囲内の最大値を取得


class segmenttree{
public:
    long long INF = 1e18;
    long long siz = 1;
    vector<long long> v;
    segmenttree (long long n){
        siz = 1;
        while(siz < n)siz *= 2;
        v.assign(2*siz,-INF);
    }
    void update(long long i, long long x){
        i += siz;
        v[i] = x;
        while(i > 1){
            i /= 2;
            v[i] = max(v[i*2],v[i*2+1]);
        }
    } 
    long long query(int l,int r){
        return query(l,r,1,0,siz-1);
    }
    private : 
    long long query(int L,int R,int s,int l,int r){
        long long ans = -INF;
        if(r < L || l > R)return -INF;
        if(l >= L && r <= R){
            return v[s];
        }
        ans = max(ans,query(L,R,s*2,l,(l+r)/2));
        ans = max(ans,query(L,R,s*2+1,(l+r)/2+1,r));
        return ans;
    }
};

all/構造体/RMinQ.md

RMinQ

segmenttree 名前(サイズ)　で定義

名前.update( i , x ) で i 番目の要素を x に変更

名前.query( l , r ) で l から r の範囲内の最大値を取得

class segmenttree{
public:
    long long INF = 1e18;
    long long siz = 1;
    vector<long long> v;
    segmenttree (long long n){
        siz = 1;
        while(siz < n)siz *= 2;
        v.assign(2*siz,INF);
    }
    void update(long long i, long long x){
        i += siz;
        v[i] = x;
        while(i > 1){
            i /= 2;
            v[i] = min(v[i*2],v[i*2+1]);
        }
    } 
    long long query(int l,int r){
        return query(l,r,1,0,siz-1);
    }
    private : 
    long long query(int L,int R,int s,int l,int r){
        long long ans = INF;
        if(l >= L && r <= R){
            ans = min(ans,v[s]);
            return ans;
        }
        if(r < L || l > R)return INF;
        ans = min(ans,query(L,R,s*2,l,(l+r)/2));
        ans = min(ans,query(L,R,s*2+1,(l+r)/2+1,r));
        return ans;
    }
};

all/構造体/RSQ.md

区間和のセグ木

segmenttree 名前(サイズ)　で定義

名前.update( i , x ) で i 番目の要素を x に変更

名前.query( l , r ) で l から r の範囲内の合計値を取得

class segmenttree{
public:
    long long siz = 1;
    vector<long long> v;
    segmenttree (long long n){
        siz = 1;
        while(siz < n)siz *= 2;
        v.assign(2*siz,0);
    }
    void update(long long i, long long x){
        i += siz;
        v[i] = x;
        while(i > 1){
            i /= 2;
            v[i] = v[i*2]+v[i*2+1];
        }
    } 
    long long query(int l,int r){
        return query(l,r,1,0,siz-1);
    }
    private : 
    long long query(int L,int R,int s,int l,int r){
        long long ans = 0;
        if(l >= L && r <= R){
            ans += v[s];
            return ans;
        }
        if(r < L || l > R)return 0;
        ans += query(L,R,s*2,l,(l+r)/2);
        ans += query(L,R,s*2+1,(l+r)/2+1,r);
        return ans;
    }
};

all/構造体/RSumQ.md

区間和のセグ木

segmenttreeで定義

update(i,x)iをxにする

query(l,r) l~rの合計を出す

class segmenttree{
public:
    long long INF = 1e18;
    long long siz = 1;
    vector<long long> v;
    segmenttree (long long n){
        siz = 1;
        while(siz < n)siz *= 2;
        v.assign(2*siz,0);
    }
    void update(long long i, long long x){
        i += siz;
        v[i] = x;
        while(i > 1){
            i /= 2;
            v[i] = v[i*2]+v[i*2+1];
        }
    } 
    long long query(int l,int r){
        return query(l,r,1,0,siz-1);
    }
    private : 
    long long query(int L,int R,int s,int l,int r){
        long long ans = 0;
        if(r < L || l > R)return 0;
        if(l >= L && r <= R){
            return v[s];
        }
        ans += query(L,R,s*2,l,(l+r)/2);
        ans += query(L,R,s*2+1,(l+r)/2+1,r);
        return ans;
    }
};

all/構造体/countmultiset.md

countが高速に行えるmaltiset

使い方はmulsisetと同じ

countがlogNで実行できる

template<typename T>
class countable_multiset{
    public :
    multiset<T> ms;
    map<T,int> cnt;
    void insert(const T& n){
        cnt[n]++;
        ms.insert(n);
    }
    void all_erase(const T& n){
        cnt.erase(n);
        ms.erase(n);
    }
    void it_erase(const T& n){
        auto it = ms.find(n);
        if(it==ms.end())return;
        cnt[n] = max(0,cnt[n]-1);
        if(cnt[n]==0)cnt.erase(n);
        ms.erase(it);
    }
    int count(const T& n){
        if(cnt.count(n))return cnt[n];
        return 0;
    }
    auto find(const T& n){
        return ms.find(n);
    }
};

all/構造体/index.md

データ構造

all/構造体/mapを使わないカウント.md

mapを使わずにカウントをする構造体

範囲forで全部回すなら使える

cnt x　

x.add(n) nをひとつ追加

x.solve() これをやらないと使えない

for(auto i : x){ iを使った処理 i は　{内容,個数}のpair }


template<class T>
class cnt {
    public : 
    vector<T> v;
    vector<pair<T,int>> ans;
    cnt(){};
    void add(T x){
        v.push_back(x);
    }
    void solve(){
        sort(v.begin(),v.end());
        ans.push_back({v[0],1});
        for(int i = 1;i < v.size();i++){
            if(v[i] == ans[ans.size()-1].first) ans[ans.size()-1].second++;
            else ans.push_back({v[i],1});
        }
    }
    auto begin() return ans.begin();
    auto end() return ans.end();
    auto begin() const return ans.begin();
    auto end() const return ans.end();
};

all/構造体/order_statistic_tree.md

order_statistic_tree

insert,erase,find,cnt,order,lower_bound,upper_bound,miman,ika

が可能



class trp{
    const long long INF = 1e18;
    struct node{
        int key;
        int priority;
        int siz;
        node* left;
        node* right;
        node(int k,int p){
            key = k;
            priority = p;
            siz = 1;
            left = nullptr;
            right = nullptr;
        }
    };

    node* root;


    bool find(node* t,int x){
        if(t == nullptr)return false;
        if(t -> key == x)return true;
        if(x < t->key)return find(t->left,x);
        else return find(t->right,x);
    }
    node* merge(node* l,node* r){
        if(l == nullptr)return r;
        if(r == nullptr)return l;
        if(l->priority > r->priority){
            l-> right = merge(l->right,r);
            update(l);
            return l;
        }
        else{
            r->left = merge(l,r->left);
            update(r);
            return r;
        }
    }
    pair<node*,node*> split(node* t,int x){
        if(t==nullptr)return {nullptr,nullptr};
        if(x <= t->key){
            pair<node*,node*> p = split(t->left,x);
            t -> left = p.second;
            update(t);
            return {p.first,t};
        }
        else{
            pair<node*,node*> p = split(t->right,x);
            t -> right = p.first;
            update(t);
            return {t,p.second};            
        }
    }
    int size(node* t){
        if(t == nullptr)return 0;
        else return t -> siz;
    }
    void update(node* t){
        if(t == nullptr)return;
        t -> siz = 1 + size(t->left)+size(t->right);
    }
    int cnt(node* t,int k){
        if(t == nullptr)return -INF;
        int lsiz = size(t->left);
        if(lsiz > k){
            return cnt(t -> left,k);
        }
        else if(k==lsiz){
            return t->key;
        }
        else{
            return cnt(t -> right,k - lsiz - 1);
        }
    }
    int order(node* t,int x){
        if(t == nullptr)return 0;
        if(x <= t->key){
            return order(t -> left,x);
        }
        else{
            return size(t -> left) + 1 + order(t->right,x);
        }
    }
    node* lower_bound(node* t, int x){
        if(t == nullptr) return nullptr;

        if(t->key < x){
            return lower_bound(t->right, x);
        }
        else{
            node* res = lower_bound(t->left, x);
            if(res != nullptr) return res;
            else return t;
        }
    }
    node* upper_bound(node* t, int x){
        if(t == nullptr) return nullptr;

        if(t->key <= x){
            return upper_bound(t->right, x);
        }
        else{
            node* res = upper_bound(t->left, x);
            if(res != nullptr) return res;
            else return t;
        }
    }
    node* ika(node* t,int x){
        if(t==nullptr)return nullptr;
        if(t -> key > x){
            return ika(t->left,x);
        }
        else{
            node*res = ika(t->right,x);
            if(res != nullptr)return res;
            else return t;
        }
    }


    public : 
    trp(){
        root = nullptr;
    }
    bool find(int x){
        return find(root,x);
    }
    void insert(int x){
        if(find(x))return;
        pair<node*,node*> p = split(root,x);
        node* r = p.second;
        node* l = p.first;
        node* n = new node(x,rand());
        root = merge(merge(l,n),r);
    }
    void erase(int x){
        if(!find(x))return ;
        pair<node*,node*> a = split(root,x);
        pair<node*,node*> b = split(a.second,x+1);
        root = merge(a.first,b.second);
    }
    int cnt(int k){
        return  cnt(root,k);
    }
    int order(int x){
        return order(root,x);
    }
    int lower_bound(int x){
        node* res = lower_bound(root, x);
        if(res == nullptr) return -INF;
        return res->key;
    }
    int upper_bound(int x){
        node* res = upper_bound(root, x);
        if(res == nullptr) return -INF;
        return res->key;
    }
    int miman(int x){
        int k = order(x) -1;
        if(k < 0)return -INF;
        return cnt(k);
    }
    int ika(int x){
        node* k = ika(root,x);
        if(k == nullptr)return -INF;
        else return k->key;
    }
};

all/構造体/treap木.md

treap木

insert

find

erase

ができる


class trp{
    struct node{
        int key;
        int priority;
        node* left;
        node* right;
        node(int k,int p){
            key = k;
            priority = p;
            left = nullptr;
            right = nullptr;
        }
    };

    node* root;


    bool find(node* t,int x){
        if(t == nullptr)return false;
        if(t -> key == x)return true;
        if(x < t->key)return find(t->left,x);
        else return find(t->right,x);
    }
    node* merge(node* l,node* r){
        if(l == nullptr)return r;
        if(r == nullptr)return l;
        if(l->priority > r->priority){
            l-> right = merge(l->right,r);
            return l;
        }
        else{
            r->left = merge(l,r->left);
            return r;
        }
    }
    pair<node*,node*> split(node* t,int x){
        if(t==nullptr)return {nullptr,nullptr};
        if(x <= t->key){
            pair<node*,node*> p = split(t->left,x);
            t -> left = p.second;
            return {p.first,t};
        }
        else{
            pair<node*,node*> p = split(t->right,x);
            t -> right = p.first;
            return {t,p.second};            
        }
    }

    public : 
    trp(){
        root = nullptr;
    }
    bool find(int x){
        return find(root,x);
    }
    void insert(int x){
        if(find(x))return;
        pair<node*,node*> p = split(root,x);
        node* r = p.second;
        node* l = p.first;
        node* n = new node(x,rand());
        root = merge(merge(l,n),r);
    }
    void erase(int x){
        if(!find(x))return ;
        pair<node*,node*> a = split(root,x);
        pair<node*,node*> b = split(a.second,x+1);
        root = merge(a.first,b.second);
    }
};

all/構造体/unionfind.md

union find

find：根を求める connect：繋げる(もともと繋がってたらfalseをreturn) same：結合か判定 size：そのノードの連結要素数


class UnionFind {
public:
	//@brief Union-Findのコンストラクタ
	//@param n ノード数
	UnionFind(int n) : PoS(n, -1) {}

	//@brief 根を求める
	//@param x ノード番号
	//@return xの根のノード番号
	int find(int x) {
		if (PoS[x] < 0) {
			return x;
		}
		return (PoS[x] = find(PoS[x]));
	}

	//@brief 接続かを判定する
	//@param x ノード1
	//@param y ノード2
	bool same(int x, int y) {
		return (find(x) == find(y));
	}

	//@brief 連結要素数を数える
	//@param x ノード番号
	//@return xの連結要素数
	int size(int x) {
		return -PoS[find(x)];
	}

	//@brief 集合を繋げる
	//@param x ノード1
	//@param y ノード2
	//@return 結合が行えたか(既に結合していた:false)
	bool connect(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return false;

		if (-PoS[x] < -PoS[y]) {
			std::swap(x, y);
		}
		PoS[x] += PoS[y];
		PoS[y] = x;
		return true;
	}
private:
	//@brief 親もしくは要素数(Parent or Size)
	std::vector<int> PoS;
};

all/構造体/xorセグ木.md

xorのセグ木

segmenttree seg(n) サイズnで定義

seg.update(i,x) i番目をxにする

seg.query(l,r) l~rの区間のxorを出す


class segmenttree{
public:
    long long INF = 1e18;
    long long siz = 1;
    vector<long long> v;
    segmenttree (long long n){
        siz = 1;
        while(siz < n)siz *= 2;
        v.assign(2*siz,0);
    }
    void update(long long i, long long x){
        i += siz;
        v[i] = x;
        while(i > 1){
            i /= 2;
            v[i] = v[i*2]^v[i*2+1];
        }
    } 
    long long query(int l,int r){
        return query(l,r,1,0,siz-1);
    }
    private : 
    long long query(int L,int R,int s,int l,int r){
        long long ans = 0;
        if(l >= L && r <= R){
            ans = ans^v[s];
            return ans;
        }
        if(r < L || l > R)return 0;
        ans ^= query(L,R,s*2,l,(l+r)/2);
        ans ^= query(L,R,s*2+1,(l+r)/2+1,r);
        return ans;
    }
};

all/構造体/区間最大遅延セグ木.md

区間最大遅延セグ木

segenttree seg(N) サイズNのセグ木を宣言 初期値-INFなのでちゃんとしといてください

初期化まじでちゃんとしてください

range_add(l,r,x) lからrまでにxを加算

range_set(l,r,x) lからrまでをxに変更

query(l,r) lからrまでの最大値を出力

計算量　　全て logN

class segmenttree{
public:
    long long INF = 1e18;
    long long siz = 1;
    vector<long long> v;
    vector<long long> lazy_add;
    vector<long long> lazy_set;
    vector<bool> hav_set;
    segmenttree (long long n){
        siz = 1;
        while(siz < n)siz *= 2;
        v.assign(2*siz,-INF);
        lazy_add.assign(2*siz,0);
        lazy_set.assign(2*siz,0);
        hav_set.assign(2*siz,false);
    }
    long long query(long long l,long long r){
        if(l > r)return -INF;
        return query(l,r,1,0,siz-1);
    }
    void range_add(long long l,long long r,long long x){
        range_add(l,r,1,0,siz-1,x);
    }
    void range_set(long long l,long long r,long long x){
        range_set(l,r,1,0,siz-1,x);
    }
    void apply_set(long long s,long long x){
        v[s] = x;
        lazy_set[s] = x;
        lazy_add[s] = 0;
        hav_set[s] = true;
    }
    void apply_add(long long s,long long x){
        v[s] += x;
        if(hav_set[s]){
            lazy_set[s] += x;
        }
        else{
            lazy_add[s] += x;
        }

    }
    void push(long long s){
        if(hav_set[s]){
            apply_set(s*2,lazy_set[s]);
            apply_set(s*2+1,lazy_set[s]);
            hav_set[s] = false;
            lazy_set[s] = 0;
        }
        if(lazy_add[s]!=0){
            apply_add(s*2,lazy_add[s]);
            apply_add(s*2+1,lazy_add[s]);
            lazy_add[s] = 0;
        }
    }
    void pull(long long s){
        v[s] = max(v[s*2],v[s*2+1]);
    }
    long long query(long long L,long long R,long long s,long long l,long long r){
        if(r < L || l > R)return -INF;
        if(l >= L && r <= R){
            return v[s];
        }
        push(s);
        long long ans = max(
            query(L,R,s*2,l,(l+r)/2),
            query(L,R,s*2+1,(l+r)/2+1,r)
        );
        return ans;
    }
    void range_set(long long L,long long R,long long s,long long l,long long r,long long x){
        if(r < L || l > R)return;
        if(l >= L && r <= R){
            apply_set(s,x);
            return;
        }
        push(s);
        range_set(L,R,s*2,l,(l+r)/2,x);
        range_set(L,R,s*2+1,(l+r)/2+1,r,x);
        pull(s);
    }
    void range_add(long long L,long long R,long long s,long long l,long long r,long long x){
        if(r < L || l > R)return;
        if(l >= L && r <= R){
            apply_add(s,x);
            return;
        }
        push(s);
        range_add(L,R,s*2,l,(l+r)/2,x);
        range_add(L,R,s*2+1,(l+r)/2+1,r,x);
        pull(s);
    } 
};

all/構造体/区間最小遅延セグ木.md

区間最小遅延セグ木

segenttree seg(N) サイズNのセグ木を宣言 初期値INFなのでちゃんとしといてください

初期化まじでちゃんとしてください

range_add(l,r,x) lからrまでにxを加算

range_set(l,r,x) lからrまでをxに変更

query(l,r) lからrまでの最小値を出力

計算量　　全て logN

class segmenttree{
public:
    long long INF = 1e18;
    long long siz = 1;
    vector<long long> v;
    vector<long long> lazy_add;
    vector<long long> lazy_set;
    vector<bool> hav_set;
    segmenttree (long long n){
        siz = 1;
        while(siz < n)siz *= 2;
        v.assign(2*siz,INF);
        lazy_add.assign(2*siz,0);
        lazy_set.assign(2*siz,0);
        hav_set.assign(2*siz,false);
    }
    long long query(long long l,long long r){
        if(l > r)return INF;
        return query(l,r,1,0,siz-1);
    }
    void range_add(long long l,long long r,long long x){
        range_add(l,r,1,0,siz-1,x);
    }
    void range_set(long long l,long long r,long long x){
        range_set(l,r,1,0,siz-1,x);
    }
    void apply_set(long long s,long long x){
        v[s] = x;
        lazy_set[s] = x;
        lazy_add[s] = 0;
        hav_set[s] = true;
    }
    void apply_add(long long s,long long x){
        v[s] += x;
        if(hav_set[s]){
            lazy_set[s] += x;
        }
        else{
            lazy_add[s] += x;
        }

    }
    void push(long long s){
        if(hav_set[s]){
            apply_set(s*2,lazy_set[s]);
            apply_set(s*2+1,lazy_set[s]);
            hav_set[s] = false;
            lazy_set[s] = 0;
        }
        if(lazy_add[s]!=0){
            apply_add(s*2,lazy_add[s]);
            apply_add(s*2+1,lazy_add[s]);
            lazy_add[s] = 0;
        }
    }
    void pull(long long s){
        v[s] = min(v[s*2],v[s*2+1]);
    }
    long long query(long long L,long long R,long long s,long long l,long long r){
        if(r < L || l > R)return INF;
        if(l >= L && r <= R){
            return v[s];
        }
        push(s);
        long long ans = min(
            query(L,R,s*2,l,(l+r)/2),
            query(L,R,s*2+1,(l+r)/2+1,r)
        );
        return ans;
    }
    void range_set(long long L,long long R,long long s,long long l,long long r,long long x){
        if(r < L || l > R)return;
        if(l >= L && r <= R){
            apply_set(s,x);
            return;
        }
        push(s);
        range_set(L,R,s*2,l,(l+r)/2,x);
        range_set(L,R,s*2+1,(l+r)/2+1,r,x);
        pull(s);
    }
    void range_add(long long L,long long R,long long s,long long l,long long r,long long x){
        if(r < L || l > R)return;
        if(l >= L && r <= R){
            apply_add(s,x);
            return;
        }
        push(s);
        range_add(L,R,s*2,l,(l+r)/2,x);
        range_add(L,R,s*2+1,(l+r)/2+1,r,x);
        pull(s);
    } 
};

all/累積和/imos.md

imos法のライブラリ

plus(l,r,x) でl~rまでにxを加算する

solve() をしたら完成

そこからは普通のvecotrと同じようにアクセスできる


class imos{
    public : 
    vector<long long> v;
    long long n;
    imos(long long x){
        v.assign(x,0);
        n = v.size();
    }
    void plus(long long l,long long r,long long x){
        v[l] += x;
        if(r != n-1)v[r+1]-=x;
    }
    void solve(){
        for(long long i = 1;i < n;i++){
            v[i] += v[i-1];
        }
    }
    long long at(long long pos){
        return v[pos];
    }
    long long operator[](long long pos) const {
        return v[pos];
    }
};

all/累積和/imos2D.md

imos2D

(a,b)(   )(   )
(   )(   )(   )
(   )(   )(c,d)

update(a,b,c,d,x)でここの範囲に+xできる

build()をやったらOK


class imos2D{
    public :
    vector<vector<long long>> v;
    long long h,w;
    imos2D(long long H,long long W){
        h = H;
        w = W;
        v.assign(h,vector<long long>(w));
    }
    void update(long long a,long long b,long long c,long long d,long long x){
        v[a][b]+=x;
        if(c+1 < h)v[c+1][b]-=x;
        if(d+1 < w)v[a][d+1]-=x;
        if(c+1 < h && d+1 < w)v[c+1][d+1]+=x;
    }
    void build(){
        for(long long i = 0;i < h;i++){
            for(long long j = 1;j < w;j++){
                v[i][j] += v[i][j-1];
            }
        }
        for(long long j = 0;j < w;j++){
            for(long long i = 1;i < h;i++){
                v[i][j] += v[i-1][j];
            }
        }
    }
    vector<long long>& operator[](long long i){
        return v[i];
    }
    const vector<long long>& operator[](long long i) const{
        return v[i];
    }
};

all/累積和/index.md

累積和

all/累積和/二次元累積和.md

二次元累積和

rui2D R(v) でvの二次元累積和を作る

R.query(a,b,c,d)で

(a,b)(   )(   )
(   )(   )(   )
(   )(   )(c,d)

の区間の累積を取る

class rui2D{
    public : 
    vector<vector<long long>> v;
    rui2D(vector<vector<long long>>& a){
        v = a;
        long long h = v.size();
        long long w = v[0].size();
        for(long long i = 0;i < h;i++){
            for(long long j = 1;j < w;j++){
                v[i][j] += v[i][j-1];
            }
        }
        for(long long j = 0;j < w;j++){
            for(long long i = 1;i < h;i++){
                v[i][j] += v[i-1][j];
            }
        }
    }
    long long query(long long a,long long b,long long c,long long d){
        long long ans = v[c][d];
        if(a!=0)ans -= v[a-1][d];
        if(b!=0)ans -= v[c][b-1];
        if(a!=0 && b != 0)ans += v[a-1][b-1];
        return ans;
    }
};

all/累積和/累積和.md

累積和をやるためのライブラリ

rui R(v)でvを累積和にしたRを作れる

queryで(l,r)の範囲の和を求められる

template<typename T>
class rui{
    public:
    vector<T> v;
    rui(const vector<T>& a){
        v = a;
        for(int i = 1;i < a.size();i++){
            v[i] += v[i-1];
        }
    }
    T query(int l,int r){
        if(l == 0){
            return v[r];
        }
        else{
            return v[r] - v[l-1];
        }
    }
};

index.md

template.md

よく使うやつ

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using ll = long long;
#define rep(i , n) for(int i=0; i< (int)(n); i++)
#define int long long
const ll INF = 1e18;
const int inf = 1e9;
const int mod = 998244353;
template<class T>
void chmin(T& a, T b){ if(a > b) a = b; }
template<class T>
void chmax(T& a, T b){ if(a < b) a = b; }
void yes(){cout << "Yes" << endl;}
void no(){cout << "No" << endl;}
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
}

ライブラリindex.md

ライブラリ全文.md

Kansu C++ Library — Full Dump for AI

{% assign md_pages = site.pages | where_exp: “p”, “p.path contains ‘.md’” | where_exp: “p”, “p.name != ‘ai_all.md’” | sort: “path” %}

{% for p in md_pages %}

{{ p.path }}

{{ p.content }}

{% endfor %}

一覧.md

ライブラリ一覧

{% assign genres = “数学,累積和,グラフ,構造体,二分探索,その他典型” split: “,” %}

{% for genre in genres %}

{{ genre }}

{% endfor %}

典型解説/XOR.md

XORの性質

XORキャンセル

XORはもう一度同じものをXORすることでキャンセルをすることができる

累積XOR

XORも累積和と同じように累積を取りことができる

XORキャンセルを使って累積の部分のXORを計算できる

XOR和 = 和　になる場合

この場合全ての要素についてそれぞれの桁についてbitが立っているのは一個だけであるのが確定するので、その範囲内では部分列も同じことが成り立つ

典型解説/index.md

典型解説

典型解説/二分探索.md

二分探索

中央値の二分探索

ABC 107 D

中央値を小さい方から数えて ⌈n/2⌉番目とする

基準となる値を決めることで全ての配列の値をmidを超えるな超えないかの1,-1で表すことができる

その総和が1以上のとき中央値は基準となる値を超えることが言える

これを使えば中央値がX以上かという判定問題をO(N)で解け、二分探索に応用できる

平均値での二分探索

ABC 236 E

これも中央値と同じように基準となる値との差の総和と考える

平均値がXを超えるかという判定をO(N)でできる

並列二分探索

ABC394 G

同じ条件での二分探索が複数個ある場合、同一の値を使った判定を解いていくことで高速化できる

クエリの数をQ,答えの最大値をM,判定にかかる時間をO(1),毎回の初期化にかかる時間をNとするならO(Qlog(M+N))で終わらせることができる

典型解説/全探索.md

全探索

多重ループ全探索

ABC 123 D

全探索中に結果に関係しないことが確定するものを除外することで時間内に全探索をすることができる

順列全探索

ABC 198 D

O(10!)程度の計算量なのでゴリ押せる

next_permutationを使うと簡単に実装することができる

再帰全探索

DFSを用いて全探索を行う

典型解説/半分全列挙.md

半分全列挙

多数の対象を少量使用する場合

JOI 2008 本選

全探索とほとんど変わらない

ビット全探索による半分全列挙

典型90 51

ビット全探索を使って半分全列挙をし、その結果を二分探索などで高速に処理する

BFS　の半分全列挙

第19回アルゴリズム技能検定

BFSで決められた深さの半分まで潜ることをスタートとゴールの両方から行うことで全列挙を高速に行うことができる

偶奇で分けて半分全列挙

ABC 326 F

偶奇で分けてそれぞれ独立で考えることで実行時間内に終わらせられる

典型解説/参考文献.md

https://note.com/rikimarublack/n/n3074b0955e95