Learning Algorithms

アルゴリズムの勉強メモ

全方位木dp

全方位木dpについてです。基本的にここにまとまっていて、僕自身もこの記事から学びました。本記事では、これよりもわかりやすく簡潔な実装します。名前が大げさですが、普通の木dpを少し拡張するだけです。上のサイトの例題 $1$ にもありますが、次のような…

木の辺の最大値のダブリング

木上のパスが含む辺の中で、その重みの最大値(最小値)を対数時間で求めるライブラリです。よく知られたダブリングというテクニックを使っています。ダブリングについてはここでは書きませんが、parmax[k][u] というのは、頂点 $u$ から根に向かってパスを $2…

二重頂点連結成分分解木

二重頂点連結成分分解木のライブラリです。誰も使わないと思います。これの続きです。任意の無向グラフから二重頂点連結成分と関節点を頂点とする木を構築できます。それをやってくれるライブラリです。 //e2i[edge] -> index of the edge //tree index : [0…

二重頂点連結成分分解

二重頂点連結成分分解の実装です。追記:誤りがあったので大幅に変更しました。名前が似ていますが、二重辺連結成分分解とは異なります。そちらについてはこの記事をご覧ください。任意の無向グラフを、その部分グラフであって「その部分グラフにおける関節…

二重辺連結成分分解

二重辺連結成分分解の実装です。二重頂点連結成分分解についてはこちらの記事をご覧ください。無向グラフ上で、橋が存在しない部分グラフを一つの頂点につぶすと、橋を辺とする木ができます。以下は、それをそのまま実装しています。 struct LowLink { set<pair<int, int>> </pair<int,>…

Atcoder Petrozavodsk Contest 001 H. Generalized Insertion Sort

H - Generalized Insertion Sort 解法 まず制約に注目すると、$25000 \geq n \log n$ にしか見えないので、そのような計算回数を実現するアルゴリズムを考えたい気持ちになります。木に関するアルゴリズムであって、計算量に $\log$ が現れるものは僕は現時…

CS Academy 069 D. Cover the Tree

CSA

CS Academy 解法 木を最小個数のパスで被覆する問題。選ぶパスは重複して良いことに注意します(もし重複を許さないなら、それはオイラー閉路を適切に構築してそれを出力する問題です)。とりあえず、葉は必ずパスの端点として選ぶ必要がありそうです。よっ…