Open15

(中~高難易度)アルゴリズム集

ピン留めされたアイテム

概要

ABCで出てきたそこそこ難しそうなアルゴリズムや、簡単なアルゴリズムの応用をまとめてます
アルゴリズムと出会って理解でき次第逐次追加

いいねとかしてくれると僕が競プロを続けるモチベになるのでしてくれると嬉しい

トポロジカルソート

(前提:多重辺なし)
入力数0の頂点をqueなどで管理(優先度付きで辞書順)しながら答えに追加。その頂点から出る辺の目的地の入力数を全て-1して、そこで入力数が0になったらqueに追加。
queが空になった時に、まだ入力数がある頂点があったらトポロジカルソート不可。

01-BFS

BFSの亜種(dequeを使う)
最小の操作回数で目的地につきたい時などに使う。
次の場所が操作なしでいける場合、そのdist_nextはdist_nowと同じでpush_front。操作が必要なら+1してpush_back。pushする時はその条件を確認(chminがtrueか、など)

貪欲法

※ガチ

ある課題に対して貪欲に「その状態に対して直後に最もいい影響を与えるもの」を選び続ける
物凄い簡単なアルゴリズムだけど、ちゃんと考えて使わないと危険なアルゴリズムでもある

このように、直感に頼った未証明のGreedyは危険です。

BFS/DFSを使った状態列挙

ある状態 S_tから、操作一つでS_{t+1}にできて、S_nで存在しうる状態全てを列挙したい時に使える
アルゴリズムは基本的にグラフ探索のものと同じ

while(!que.empty()){
    auto now = que.front(); que.pop();
    if(/*状態が S_n である*/){
        // 処理
    }
    else{
        // 隣接する状態を追加
    }
}

期待値は確立の逆数

ある試行があって、そのうちのある状態になる確率をPとした時、その試行を繰り返してその状態にするまでの試行回数期待値は\frac{1}{P}

かなり意外

区間スケジューリング問題

区間を持つものを取る時、まずそれを終点でソートして貪欲に行く。
ある区間を持つものを重複なくなるべく多く取る問題、あるいはそれに帰着できる問題に使う

ビット全探索

2進数の性質を使った全探索
全ての項目について0か1を割り当てて判断する
O(2^N)なので、N≤20程度じゃないと間に合わない

ビット全探索
rep(bit, 1 << n){
    rep(i, n){
        if(bit & 1 << i) // フラグが立っているかの判断
    }
}

UnionFind

要素をグループ分けするときにつかう。主な機能は次の三つ

  • root(x)でxの属するグループの根を取得
  • size(x)でxの属するグループの要素数を取得
  • unite(x,y)でxとyを同じグループにする(=xが属するグループとyが属するグループを統合する)

「uniteで大きい方のグループに統合」「rootで経由する要素の情報も書き換える」の二つでかなりの高速化できる(アッカーマン関数の逆関数らしい)
(最近ハマってるラムダ式で書く)
案外簡単にかけるデータ構造

UnionFind
vector<int>uf(n, -1); // 非負整数で根、負数でサイズ

function<int(int)>root = [&uf, &root](int x){
    if(uf[x] < 0) return x; // 自身が根
    uf[x] = root(uf[x]);
    return uf[x];
};

function<int(int)>size = [&uf, &root](int x){
    return -uf[root(x)];
};

function<void(int, int)>unite = [&uf, &root, &size](int x, int y){
    if(size(x) < size(y)){ // yに揃える
        uf[root(y)] += uf[root(x)];
        uf[root(x)] = y;
    }
    else { // xに揃える
        uf[root(x)] += uf[root(y)];
        uf[root(y)] = x;
    }
}

尺取り法

ある条件を満たす範囲の大きさの最大値を求める時とかに使う。ざっくりいうと、

  • 条件を満たすなら右端を
  • 条件を満たさないなら左端を
    右にずらし続けるアルゴリズム
    なので、特別な事情がない限りwhile1つで綺麗にかける(半開区間に注意)
尺取り
int l = 0, r = 0;
while(l < n){
    if(r==n || 条件){
        ++l;
    }
    else{
        ++r;
    }
}

あとは適当な処理を適当な場所に埋め込んどく

手順問題は逆順に

ある手順があって、それを実行したあと(または途中)の状況を出力する問題の時、クエリを全て逆順にしてあげると簡単になることが多い。
おそらく典型技法

座標圧縮

座圧。
a[i] ← aの中でa[i]が何番目に大きいか
となるように変換する。手順↓

  1. 配列をコピー
  2. mapで値-添字の組を保存
  3. コピーした配列をソート
  4. ソートした配列を順に辿って、mapに保存した値を見ながら代入していく
座圧
vector<ll>a;
vector<ll>b = a; // 1.

// 2.
map<ll,vector<ll>>mp;
for(ll idx=0; ll i : a){
    mp[i].push_back(idx);
}

// 3. 
sort(ALL(b));

// 4.
for(ll idx=0; ll i : b){
    for(auto j : mp[i]) a[j] = idx;
    ++idx;
}

ダイクストラ法

重み付きグラフの一点から全点に対する最短距離をO(|E|log|V|)で求めるBFS亜種(E:辺の集合/V:頂点の集合)
ポイント
・優先度付きqueueを使って点、距離の情報を格納して、「始点から近い点を順に辿る」という操作を実現
・ある点に訪れているときにはすでにその点の最短距離は確定している(その点につながる、その点より距離が近い点は全て確認済みなので)

この二つを意識しながらBFS亜種を書く

Dijkstra
int main(){
    vector<vector<pair<ll,ll>>> G(n); // グラフ (fir:頂点, sec:距離)
    // グラフ入力

    vector<ll>dist(n, INF); // 距離
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>>que; // 最小値を取り出すqueue
    dist[0] = 0; // 始点
    que.push(make_pair(0, 0)); // 始点の情報を追加

    while(!que.empty()){
        // 1. まだ訪れていない頂点のうち、最も始点から近い点を取り出す
        auto [d, now] = que.top(); que.pop();

        // 2. すでに確定している距離ではない(=すでにその頂点を訪れている)場合、パス
        if(d > dist[now]) continue;

        // 3. 頂点を列挙
        for(auto [i, j] : G[now]){
            // 4. すでにある距離より長くなりそうならパス(追加する必要はない)
            if(dist[i] <= dist[now]+j) continue;

            // 5. 距離を更新(ちなみに、絶対に短くなるのでchminとかは要らない)
            dist[i] = dist[now]+j;

            // 6. queに追加
            que.push(make_pair(dist[i], i));
        }
    }
}

ダブリング

この記事みて

概要:
連続した状況がある時、ある時点iiにおいてそのK回先の状況を求めるのにはO(K)の時間がかかる場合に、ありうる状態数をNとしたときに前処理O(NlogK)、クエリO(logK)で求めるアルゴリズム

強連結成分分解(SCC)

ある有向グラフから「任意の2点について互いに行き来可能(=強連結)」となるように分解するもの。以下のようにして処理する

  1. DFSで帰りがけ順に頂点を記録
  2. グラフの辺を逆順に張り直し、1.で記録した順でDFSを行う(ただし訪問済みはスキップ)
  3. この探索1回で探索できた頂点が強連結成分になる

この操作の後、連結成分をそれぞれ1つににまとめてDAG(ループのない有向グラフ)にするのが典型らしい

プログラム例(グループ分けをするだけ)
resultの部分を変えればいろんなことができそう
(それぞれの連結成分の要素数のカウント / 2次元配列にまとめる etc...)

vector<vector<ll>>G(n); // 順方向に辺が張られたグラフ
vector<vector<ll>>Gr(n); // 逆方向に辺が張られたグラフ

// グラフの入力

stack<ll>stk; // 帰りがけ順に記録する
vector<ll>visited(n); // 訪問済みかどうか

// 1. 探索順を決める
function<void(ll)>dfs1=[&](ll now){
    if(visited[now]) return;
    visited[now] = 1;
    for(auto i : G[now]) dfs1(i);
    stk.push(now);
}
rep(i, n) dfs1(i);

// 2. もう一度DFSをして分解
visited.assign(n);
vector<ll>result(n, -1); // どの頂点がどのグループに属するか
function<void(ll)>dfs2=[&](ll now, ll id){
    if(visited[now]) return;
    for(auto i : Gr[now]) dfs2(i, id);
    result[now] = id;
}
rep(i, n) dfs2(i, i);
作成者以外のコメントは許可されていません