記録

[Katsudon10]

勉強したことや参考したURLなど

[Katsudon10]

UnionFindを実装

struct UnionFind{
   vector<int> par,rank,siz;
   UnionFind(int n) : par(n,-1),rank(n,0),siz(n,1){ }

   int root(int x){
       if(par[x]==-1)return x;
       else return par[x]=root(par[x]);
   }

   bool issame(int x,int y){
       return root(x)==root(y);
   }

   bool unite(int x,int y){
       int rx=root(x),ry=root(y);
       if(rx==ry)return false;
       if(rank[rx]<rank[ry])swap(rx,ry);
       par[ry]=rx;
       if(rank[rx]==rank[ry])rank[rx]++;
       siz[rx]+=siz[ry];
       return true;
   }

   int size(int x){
       return siz(root(x));
   }
};

[Katsudon10]

dfs(深さ優先探索)

void dfs(Graph &G,int v,vector<bool> &seen){
    seen[v]=true;
    for(int vs:G[v]){
        if(seen[vs])continue;
        dfs(G,vs,seen);
    }
}

[Katsudon10]

DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】

DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】

[Katsudon10]

BFS(幅優先探索)

Graph G(n);
vector<int>dist(n,-1);
queue<int>que;

dist[0]=0;
que.push(0);

while(!que.empty()){
    int v=que.front();
    que.pop();
    
    for(int vs:G[v]){
        if(dist[vs]!=-1)continue;
        dist[vs]=dist[v]+1;
        que.push(vs);
    }
}

[Katsudon10]

BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜

[Katsudon10]

ダイクストラ法

WeightedGraph G(n);
vector<ll>dist(n,INF);
using P = pair<ll,int>;
priority_queue<P,vector<P>,greater<P>> que; //昇順になるようにする
dist[0]=0;
que.emplace(0,0);

while(!que.empty()){
    ll d=que.top().first;
    int v=que.top().second;
    que.pop();
    if(d>dist[v])continue; //queに入れた後にdist[v]が更新されていれば使わずスキップ
    for(auto vs:G[v]){
        ll nd=d+vs.cost;
        if(nd>=dist[vs.to])continue; //現在の最短距離と点vsを通ったときの距離を比べdist[vs.to]のほうが小さければスキップ
        dist[vs.to]=nd;
        que.emplace(nd,vs.to);
    }
}

[Katsudon10]

bit全探索(nが30ぐらいまで)

for(int bit=0;bit<(1<<n);bit++){ //2のn乗通り調べる
        int sum=0;
        for(int i=0;i<n;i++){ //bitのi番目が1かどうか
            if(bit & (1<<i)){
                sum+=a[i];
            }
        }
        if(sum==k)ans++;
}

ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜

[Katsudon10]

繰り返し二乗法

ll power(ll a,ll b,ll m){
    ll p=a,ans=1;
    rep(i,60){
        if(b&(1LL<<i)){
            ans=(ans*p)%m;
        }
        p=(p*p)%m;
    }
    return ans;
}

bが10の9乗以下ならiは30回，10の18乗以下ならiは60回ループさせる．

[Katsudon10]

二分探索

int left=0,right=l;
while(right-left>1){
    int mid=left+(right-left)/2;
    bool flag=check(mid);
    if(flag)left=mid;
    else right=mid;
}
cout << left << endl;

二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜

[Katsudon10]

Segment Tree (RMQ(Range Minimum Query))

class SegmentTree{
    public:
    vector<int>dat;
    int siz=1;

    void init(int N){
        siz=1;
        while(siz<N)siz*=2;
        dat=vector<int>(2*siz,0);
    }

    void update(int pos,int x){
        pos=pos+siz-1;
        dat[pos]=x;
        while(pos>=2){
            pos/=2;
            dat[pos]=max(dat[pos*2],dat[pos*2+1]);
        }
    }

    int query(int l,int r,int a,int b,int u){
        if(r<=a || b<=l)return -100000000;
        if(l<=a && b<=r)return dat[u];
        int m=(a+b)/2;
        int AnsL=query(l,r,a,m,u*2);
        int AnsR=query(l,r,m,b,u*2+1);
        return max(AnsL,AnsR);
    }
};

Segment Treeことはじめ【前編】

[Katsudon10]

二項係数(nCk)の計算
パスカルの三角形を使う．

vector<vector<ll>>c(61,vector<ll>(61));
c[0][0]=1;
rep(i,60){
    rep(j,i+1){
        c[i+1][j]+=c[i][j];
        c[i+1][j+1]+=c[i][j];
    }
}

二項係数とパスカルの三角形の関係

[Katsudon10]

トポロジカルソート

Graph g(n);
vector<int>deg(n,0);
rep(i,m){
    int x,y;
    cin >> x >> y;
    g[x].push_back(y);
    deg[y]++;
}
queue<int>que;
rep(i,n)if(deg[i]==0)que.push(i);
vector<int>order;
while(!que.empty()){
    int v=que.front();

    que.pop();
    order.push_back(v);
    for(int vs:g[v]){
        deg[vs]--;
        if(deg[vs]==0)que.push(vs);
    }
}
for(int v:order)cout << v << endl;

トポロジカルソート

[Katsudon10]

Warshall-Floyd　全頂点間最短路
スタートが多点の時

dpをINFで初期化
aからbへtで行けるときdp[a][b]=tで初期化
aからaは0で初期化

vector<vector<ll>>dp(n,vector<ll>(n,INF));
rep(i,n)dp[i][i]=0;
rep(i,m){
    int a,b,t;
    cin >> a >> b >> t;
    a--,b--;
    dp[a][b]=t;
    // dp[b][a]=t; 無効グラフの時
}

rep(k,n){
    rep(i,n){
        rep(j,n){
            chmin(dp[i][j],dp[i][k]+dp[k][j]);
        }
    }
}

[Katsudon10]

クラスカル法
重みが最小の全域木を求める

using kEdge = pair<int,pair<int,int>>;

int v,e;
cin >> v >> e;
vector<kEdge>edge(e);
rep(i,e){
    int s,t,w;
    cin >> s >> t >> w;
    edge[i]=kEdge(w,make_pair(s,t));
}
sort(ALL(edge));
ll ans=0;
UnionFind uf(v);
rep(i,e){
    int w=edge[i].first;
    int s=edge[i].second.first;
    int t=edge[i].second.second;
    if(!uf.issame(s,t)){
        uf.unite(s,t);
        ans+=w;
    }
}
cout << ans << endl;

最小全域木問題(クラスカル法とプリム法)

[Katsudon10]

尺取り法

int right = 0;     
for (int left = 0; left < n; ++left) {
    while (right < n && (right を 1 個進めたときに条件を満たす)) {
        /* 実際に right を 1 進める */
        // ex: sum += a[right];
        ++right;
    }

    /* break した状態で right は条件を満たす最大なので、何かする */
    // ex: res += (right - left);

    /* left をインクリメントする準備 */
    if (right == left) ++right;
    // ex: else sum -= a[left];
}

しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ

[Katsudon10]

Bellman-Ford
重みが負であっても最短経路を求める．
負閉路がある時知らせる．

n回更新を行い，n回目に更新があれば負閉路がある．

WeightedGraph g(v);
rep(i,e){
int s,t,d;
    cin >> s >> t >> d;
    g[s].push_back(Edge(t,d));
}

bool flag=false;
vector<ll>dist(v,INF);
dist[r]=0;
rep(i,v){
    bool cycle=false;
    rep(e,v){
        if(dist[e]==INF)continue;
        for(auto vs:g[e]){
            if(chmin(dist[vs.to],dist[e]+vs.cost))cycle=true;
        }
    }
    if(i==v-1 && cycle)flag=true;
}
if(flag)cout << "NEGATIVE CYCLE" << endl;
else rep(i,v){
    if(dist[i]==INF)cout << "INF" << endl;
    else cout << dist[i] << endl;
}

[Katsudon10]

三分探索
一つしか極値のない関数fにおける極値を探索するアルゴリズム

ll l = 0, r = INF;
while (r - l > 2) {
    ll c1 = (l * 2 + r) / 3; // 1/3の点
    ll c2 = (l + r * 2) / 3; // 2/3の点
    if (f(c1) > f(c2)) l = c1;
    else r = c2;
}
double ans = a;
// lからrまでの3点の中から一番低い点が答え
for (ll i = l; i <= r; i++) {
    ans = min(ans, f(i));
}