Baby Stepsなブログ

http://hos.ac/slides/20140319_bit.pdf

実装

※ 要 Binary Index Tree

pione.hatenablog.com

/// 転倒数
long long inversion_number(const vector<long long>& v){
  auto u=v;
  sort(u.begin(), u.end());
  u.erase(unique(u.begin(), u.end()), u.end());
  
  auto bit=BIT<long long>(u.size());
  
  long long res=0;
  for(int i=0; i<v.size(); i++){
    int rank=lower_bound(u.begin(), u.end(), v[i])-u.begin()+1;
    res+=i-bit.sum(rank);
    bit.add(rank);
  }
  return res;
}

座標圧縮の実装に関する個人的なメモ

座標圧縮の実装箇所において、地味に実装バグのトラップとなる箇所があるのでメモしておく。

1. unique 呼び出し前には必ずソート

未ソートの状態でもuniqueは当然呼び出し可能だが、この場合、隣り合った重複要素だけが取り除かれる。

つまり、↓のように完全に重複が除去されない可能性がある。

a a a a a b b b b b a => a b a

cpprefjp.github.io

2. erase の引数

  u.erase(unique(u.begin(), u.end()), u.end());

上記のeraseは↓のように第二引数を忘れてもコンパイルが通ってしまう。

  u.erase(unique(u.begin(), u.end()));

この場合のeraseの挙動は、uniqueが返す index の1つの要素のみを削除する。

1 or 2 のミスを犯すことで、重複が完全に除去されずに残ってしまい、後の二分探索が正常に動作せずバグが生じる。

2021-01-31

BIT（Binary Index Tree）の実装

C++ アルゴリズムライブラリ競技プログラミング

他ライブラリ（転倒数等）で活用されることがあるので置いておく。

前提

Fenwick Treeとも
競プロにおいては、BITでできることは以下の2点であると抑えておこう。
- 累積和テーブルの更新: add
- 指定した区間の累積和の計算: sum
機能を限定することで扱いやすくしたセグメント木ととも捉えられる。（BITでできることは基本セグ木でもできる）
BITの実装の特性から、データ構造の開始の添え字は1になっている。（詳しくは下の解説PDFを参照）

BITのわかりやすい解説

実装

/**
 * Binary Index Tree
 * パラメータの添え字は全て1-indexである点に注意する
 */
template<typename T>
class BIT {
  private:
  int n;
  vector<T> d;
  
  public:
  BIT(int n=0):n(n),d(n+1) {}
  
  /// i以降の累積和にxを加算
  void add(int i, T x=1) {
    for (; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  
  /// 閉区間[1,i]の累積和を求める
  T sum(int i) {
    T x = 0;
    for (; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  
  /// 閉区間[l,r]の累積和を求める
  T sum(int l, int r) {
    return sum(r) - sum(l-1);
  }
};

検証用問題

余談

  BIT(int n=0):n(n),d(n+1) {}

完全に余談ですが、上記の様なコンストラクタの初期化形式をメンバイニシャライザと呼びます。（度々通称を忘れてしまうのでメモ）

2021-01-30

最長共通接頭辞（Z-Algorithm）のライブラリを作った

C++ アルゴリズムライブラリ競技プログラミング

今まで文字列照合系問題は、DP(LCS)で頑張っていたけど、持っていたら便利そうだと思ったのでライブラリを用意してみた。

前提

Z-Algorithmとは、最長共通接頭辞の長さを線形時間で求めるアルゴリズム。

文字列の長さをnとして、O(n²)を、O(n)に改善できる
既に算出済みの長さを利用して効率化を図る
基本的な発想は、Z[i]:=iからの共通接頭辞の長さ、として、Z[i], Z[j]の値が一致するなら、i < i+k < i+Z[j] なるkについて、Z[j+k] は Z[i+k] に一致するから再利用しようというもの
例外が2つある
- i側であるindex:x(∈[i+1,i+Z[i]])を定めた時、xから始まる共通接頭辞がi+Z[i]を超える場合
- j側でも同様に、j+Z[j]を超えて一致する場合

Z-Algorithmのわかりやすい解説

snuke.hatenablog.com

scrapbox.io

実装

// Z-Algorithm
vector<int> Z;

int z_algorithm(const string& s){
  int n=s.size();
  Z.clear();
  Z.resize(n);
  
  Z[0]=n;
  int i=1, j=0; // i:今見ているindex, j:iから一致する共通接頭辞の長さ
  while(i<n){
    while(i+j<n and s[j]==s[i+j]) j++; // iから愚直に接頭辞の長さを求める
    Z[i]=j;
    if(j==0){
      i++;
      continue;
    }
    int k=1;
    while(i+k<n and k+Z[k]<j){ // Z[k]からの長さがjに完全に含まれるなら（終端は含まない）、Z[i+k]はZ[k]と一致する
      Z[i+k]=Z[k];
      k++;
    }
    i+=k; // Z[i+k]=Z[k]で埋めた最後のindexの次にカーソルを移動
    j-=k; // [i,i+j]は共通接頭辞で、前からkまで検査済みなので、Z[i+k]は少なくともj-k以上になる
  }
  
  return *max_element(Z.begin(), Z.end());
}

検証用問題

atcoder.jp

素集合データ構造（Union-Find木）の実装

C++ ライブラリ競技プログラミングアルゴリズム

クラスカル法など、他ライブラリから呼ばれることがあるので実装を置いておく。

前提

グループの管理を高速で行うことができるデータ構造
実態は木（森）になっている
ある状態から、グループを併合することができ、分割することはできない
UnionFind木の機能は基本的に2つである
- unite（以下の実装ではconnect）：要素(a,b)のグループを併合する
- is_same：要素(a,b)が同じグループに属しているかを返す
計算量改善に2つの工夫がなされている（下に載せたAtCoder社のスライドに図解がある）
- 経路圧縮：同一グループの頂点を1つの根に直接繋ぐ
- ランク：併合の際、小さいグループを大きいグループに併合する
以上の2点によりunite, isSameは、ならし計算量でO(α(n))となる（α(n)はアッカーマン関数の逆関数でlog_nよりも高速）
小さいグループを大きいグループに併合するテクは、マージテクとも呼ばれ、これ単体が解法となる問題もあるほど重要

わかりやすい解説

Union find(素集合データ構造) from AtCoder Inc.

www.slideshare.net

chokudaiさんによる解説放送

検証用問題

実装

class UnionFind {
private:
  vector<int> parent;

public:
  UnionFind(int n) { parent = vector<int>(n, -1); }

  int root(int a) {
    if (parent[a] < 0)
      return a;
    return parent[a] = root(parent[a]);
  }

  int size(int a) { return -parent[root(a)]; }

  bool connect(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) {
      return false;
    }
    if (size(a) < size(b))
      swap(a, b);
    parent[a] += parent[b];
    parent[b] = a;
    return true;
  }

  bool is_same(int a, int b) { return root(a) == root(b); }
};

忘れがちだった最小全域木のコストを求めるアルゴリズム（クラスカル法、プリム法）をライブラリ化した

ライブラリ C++ 競技プログラミングアルゴリズム

前提

いずれも発想は貪欲法である。

クラスカル法

実装内容の理解についてはクラスカル法の方が楽
頂点数に対応する大きさのUnionFind木を用意する
グラフの辺を、重みの小さい順に見ていき、(u, v)がまだ同じグループに属していないならばその辺を採用することを繰り返す
上記を全ての辺について行うと最終的に最小全域木のコストが求まる
ボトルネックは辺のソート部分のため、辺数をE、頂点数をVとして O(ElogE) と覚えておけばよい（厳密にはO(ElogV）

クラスカル法のわかりやすい解説

プリム法

空集合Sを作り、元の頂点集合Vから任意に1個をSに追加する
今集合Sから延びる辺で、Sに無い頂点へ延びる辺のうち最小のものを最小全域木の辺として採用し、その頂点をSに追加する
↑の処理はナイーブに実装するとO(V^2)だが、優先度キューを用いることでO(ElogV)になる
こちらも感覚的にはO(ElogE)と覚えておけばよい
- 全ての辺を見て優先度キューに追加する（O(ElogE)）
- 最小コストの辺を取得する（O(logE)）

プリム法のわかりやすい解説

検証用問題

以下の2つのライブラリは、コンストラクタにグラフGを与えたのち、getを呼ぶだけで良い。

実装（クラスカル法）

※ 要 UnionFind木

pione.hatenablog.com

/* UnionFind */

class Kruskal{
  private:
  long long cost=0;
  
  public:
  Kruskal(const vector<vector<pair<int, long long>>>& G){
    int n=G.size();
    vector<tuple<long long, int, int>> V;
    for(int i=0; i<n; i++){
      for(auto p: G[i]){
        int v=p.first, c=p.second;
        V.emplace_back(c,v,i);
      }
    }
    
    sort(V.begin(), V.end());
    
    UnionFind uf=UnionFind(n);
    for(auto e: V){
      long long c; int u, v; tie(c,u,v)=e;
      if(!uf.is_same(u, v)){
        cost+=c;
        uf.connect(u, v);
      }
    }
  }
  
  long long get(){
    return cost;
  }
};

実装（プリム法）

class Prim{
  private:
  long long cost=0;
  vector<bool> used;
  
  public:
  Prim(const vector<vector<pair<int,long long>>>& G, const int root=0){
    int n=G.size();
    used.resize(n);
    used[root]=1;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
    for(auto p: G[root]){
      int v=p.first; long long c=p.second;
      if(!used[v]){
        q.emplace(c, v);
      }
    }
    while(!q.empty()){
      int v; long long c; tie(c, v)=q.top(); q.pop();
      if(!used[v]){
        used[v]=1;
        cost+=c;
        for(auto p: G[v]){
          int nv=p.first; long long nc=p.second;
          if(!used[nv]){
            q.emplace(nc, nv);
          }
        }
      }
    }
  }
  
  long long get(){
    return cost;
  }
};

satanic0258.hatenablog.com

ダブリングによる最近共通祖先（Lowest Common Ancestor）のライブラリを作った

アルゴリズム競技プログラミング C++ ライブラリ

前提

ダブリング手順

dp[i][j]:=頂点iの2^j個上の頂点
- iは頂点数nに対して、log_n
- 初期化: まずdpを-1で初期化したのち、dp[0][j]、つまり1個上のノードを登録する
- 以降、dp[i+1][j]=dp[i][dp[i][j]] で更新

ダブリングのわかりやすい解説

ダブリングによる木の最近共通祖先（LCA：Lowest Common Ancestor）を求めるアルゴリズム | アルゴリズムロジックalgo-logic.info

LCA手順

まず与えられる(u, v)の深さを揃える（深い方をrootに向けて移動させる。ここでは uが深いという前提）
- 揃える処理をナイーブに実装するなら O(n): nは頂点数
- 深さの差をdとし2進表記した時、立っているbitの位置をkとすると、u=dp[k][u] という更新を繰り返すことで深さを揃えられる
- この操作回数は高々log_n
深さを揃えた結果、u, v が一致するならLCAはu（またはv）
そうでなければ、u, vをrootに向けてLCAの一歩手前まで移動させていく
- この操作もナイーブに実装すると O(n)
- ダブリングで求めたテーブルを使い、iを大きい方から始めて、dp[i][u]!=dp[i][v] となる場合、u,vを2ⁱ個分移動させることを繰り返す。最終的なu,vの1個上のノードがLCAになる
- 上の操作回数は高々log_n

なぜdだけ移動させるのに、dのbitに着目すると良いの？

繰り返し二乗法と同じ
例で考えるとわかりやすい
- d=5だけ移動させたい
- 5=(101) であり、立っているbitに着目すると、2⁰+2²
- ダブリングで用意したテーブルを使うことで、↑の操作を再現でき、その操作回数は ⌊log_d⌋ + 1 回になっている

LCAのわかりやすい解説

検証用問題

実装

/**
 * Lowest Common Ancestor
 */
class LCA{
  private:
  int root;
  int k; // n<=2^kとなる最小のk
  vector<vector<int>> dp; // dp[i][j]:=要素jの2^i上の要素
  vector<int> depth;  // depth[i]:=rootに対する頂点iの深さ
  
  public:
  LCA(const vector<vector<int>>& _G, const int _root=0){
    int n=_G.size();
    root=_root;
    k=1;
    int nibeki=2;
    while(nibeki<n){
      nibeki<<=1;
      k++;
    }
    // 頂点iの親ノードを初期化
    dp = vector<vector<int>>(k+1, vector<int>(n, -1));
    depth.resize(n);
    function<void(int, int)> _dfs=[&](int v, int p){
      dp[0][v]=p;
      for(auto nv: _G[v]){
        if(nv==p) continue;
        depth[nv]=depth[v]+1;
        _dfs(nv, v); 
      }
    };
    _dfs(root, -1);
    // ダブリング
    for(int i=0; i<k; i++){
      for(int j=0; j<n; j++){
        if(dp[i][j]==-1) continue;
        dp[i+1][j]=dp[i][dp[i][j]];
      }
    }
  }
  
  /// get LCA
  int get(int u, int v){
    if(depth[u]<depth[v]) swap(u,v); // u側を深くする
    if(depth[u]!=depth[v]){
      long long d=depth[u]-depth[v];
      for(int i=0; i<k; i++) if((d>>i)&1) u=dp[i][u];
    }
    if(u==v) return u;
    
    for(int i=k; i>=0; i--){
      if(dp[i][u]!=dp[i][v]){
        u=dp[i][u], v=dp[i][v];
      }
    }
    return dp[0][u];
  }
  
  int get_distance(const int u, const int v){
    int lca=get(u,v);
    return depth[u]+depth[v]-2*depth[lca];
  }
};

セグメント木の抽象化（遅延評価でない）

C++ アルゴリズム競技プログラミングライブラリ

セグメント木を抽象化したライブラリ(C++)を作成したのでまとめておく。

前提

セグメント木の実態は完全二分木
要素数nを扱いたいならn以上の2冪を葉の数とし、その数をwとすると、全体の要素数は2*w-1個となる
完全二分木において、要素i(>0)の親は(i-1)/2、子は(i+1)*2-1, (i+1)*2で参照できる
セグメント木に必要な機能は基本的にはupdateとqueryの2つだけ
- update(i, v): i番目の要素をvに更新
- query(l, r): 区間[l, r)の区間クエリを実行
セグメント木ではモノイドを管理できる。モノイドとは以下の2つの性質を同時に満たすもの。
1. 結合則が成り立つ。(A・B)・C = A・(B・C)
  - 最後に載せた問題（AtCoder Regular Contest 008 D タコヤキオイシクナール）が良い例
2. 単位元eが存在する。単位元とは任意の元Aについて、e・A = A・e = A を満たすもの。（例：乗算における1）

セグメント木のわかりやすい解説記事

www.creativ.xyz

検証用問題