全方位木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,>…

はじめに 彩色数を求めるアルゴリズムについて書きました。English version is available here. 彩色数とは 彩色数(chromatic number)とは、無向グラフにおいて、辺で繋がれた頂点同士が、互いに異なる色でなければいけないという制約のもとで、すべての頂点…

はじめに $Hirschberg's\ Algorithm$ に関する解説を丁寧に書きました。English version is available here. 問題 まず次の問題をご覧くださいCS Academy概要：各マスに数字が書かれたグリッドが与えられ、そのグリッド上で左上のマスから右下のマスまで最短…

追記 2018/01/22 ・重心を求めるアルゴリズムを変更して高速化しました。 ・最後に実践的な例題を置きました。 はじめに アリ本に載っているものよりも、（個人的に）わかりやすく整理した重心分解による分割統治法の一般形について書きます（アリ本でばっち…

お寿司をできるだけたくさん食べるアルゴリズム みなさんお寿司は好きですか？ 僕は好きです。というわけで、できるだけたくさんの種類のお寿司を食べるためのアルゴリズムについて書きます。さて、早速たくさん食べる方法について考えていきます。まずお寿…

木の重心列挙アルゴリズム English version is available here.木の重心を列挙するアルゴリズムです。重心の性質をよく知っている方にとっては自明な木$dp$を実装するだけだと思います。これで $verify$ しています。計算量は $O(n)$ です。中のアルゴリズム…

木の直径のパスを一つ挙げるライブラリ 木の直径のパスを一つ挙げるやつをライブラリ化しました。これを解いている時に必要になって、自明なのに妙に実装に時間がかかったので作りました。この問題でverify済みです。中のアルゴリズムは非常に簡単で、次の通…

平面上のロシアゲー（構築ゲー）を解くためのそこそこ一般的なテクについて この記事はCompetitive Programming Advent Calendar 2017の12月13日の記事です。 ロシアゲーとは 「ある条件を満たすものを何でもいいから一つ出力しなさい」という形式の問題のこ…

この記事はCompetitive Programming Advent Calendar 2017の12月8日の記事です。 競プロにおけるオイラー路とその応用について 目次 ・はじめに ・オイラー路とは？ ・無向グラフのオイラー路 ・有向グラフのオイラー路 ・無向オイラー路の構築 ・有向オイラ…

Inverse of factorialsをO(N)で列挙する はじめに 素数 $p$ を法として、 $n$ 以下の階乗の逆元を $O(n)$ で列挙しちゃおうというアレを知っていますか？（僕は知りませんでした。。。）（コードが読みにくくなる割には）そんなに高速になるわけではないため…