アルゴリズム紹介

ポテンシャル解析

ならし計算量を解析するテクニックとしてポテンシャル解析というものがある。 ポテンシャル解析とは何かを簡単に説明し、いくつかの簡単な解析例を示す。

経路圧縮のみを用いた union-find の計算量解析

union-find の高速化テクニックとして経路圧縮は有名である。しかし、その計算量解析は有名ではないと思う。そこで、この記事では経路圧縮のみを用いた union-find の計算量解析を行う。計算量解析にはポテンシャル解析を用いるため、予備知識としてポテンシ…

mod 平方根

素数 mod p で となる を見つけるアルゴリズムです。Cipolla のアルゴリズムというのを紹介します。平方剰余に詳しくない方はまず補足を読んで下さい。Cipolla's algorithm - Wikipedia

Treap の解析

手抜きです。

±RMQによるLCAの実装

構築 O(n) 質問 O(1) のやつ。AOJ の以下の問題で verify した。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C 基本的には euler-tour + sparse table RMQ。euler-tour したときの深さ列が ±1 で変化することを利用して高速化する。 …

Burnside の定理

Polya の定理の簡単バージョンである Burnside の定理の説明と証明をする。 群を使ってるので、最低限の群の知識はあった方がいいかも。

動的計画法入門(数え上げ)

数え上げ系の DP について説明する。 この記事は DP 初心者を対象にしている。DP やるだけみたいなことを一度でも考えたことがある人は対象にしていない。

約数の個数の総和を O(√n) で求める

$n$ の約数の個数を $d(n)$ と書くとき、 $$ D(n) = d(1)+d(2)+ \cdots + d(n) $$ は $O(\sqrt{n})$ で求められる。 $n$ 以下の正整数で $i$ を約数に持つものは $\lfloor n/i \rfloor$ 個ある。このことから $$ D(n) = \left\lfloor \frac{n}{1} \right\rfl…

約数の個数を O(n^1/3) で求める

約数列挙は $O(\sqrt{n})$ 掛かるが、約数の個数を求めるだけなら $O(\sqrt[3]{n})$ でできる。 以下のページを参考にした。 codeforces.com まず $\sqrt[3]{n}$ 以下の素数を用いて $n$ を素因数分解する。 $$ n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r} X …

Mo's algorithm

Mo’s algorithm について説明します。 Mo’s algorithm の動作の様子をアニメーションにしてみました。アニメーションを見れば、計算量解析パートは自明でしょう。IE以外なら見れると思います。 https://pekempey.github.io/mo_algorithm/mo.html Mo’s algori…

Grundy数の計算方法と使い方

この記事では Grundy 数の計算方法と使い方を説明します。 Grundy 数の原理に関してはあまり触れません。

ラグランジュの定理(群論)

この記事では群論の重要定理であるラグランジュの定理の簡単な説明と、 群論を用いたCodeforces 334 (Div. 1) B. Moodular Arithmeticの解法について説明する。 この記事は 群の定義 部分群の定義 群の位数の定義 既約剰余類群 を知っている人を対象として書…

桁DP入門

この記事では桁DPについて以下の問題を取り上げ説明する A以下の非負整数のうち、「3の倍数または3の付く」かつ「8の倍数でない」数がいくつあるか求めよ いきなりこの問題を解くのは難しいと思うので、 A以下の非負整数の総数を求める A以下の非負整数のう…

Garnerのアルゴリズム

この記事ではGarnerのアルゴリズムについて説明する。

HL分解 (Heavy-Light Decomposition)

この記事ではHL分解の原理ではなく使い方を説明する。 HL分解を使う問題例 n頂点の木が与えられる。以下の二種類のクエリが飛んでくる。 uvパス上のすべての頂点にxを加算する uvパス上の値の総和を求める 総和クエリの例。この場合は 2+3+4+9+6+4+7+1=36 が…

木の直径を求めるアルゴリズム

木の直径を求めるアルゴリズムの正当性を確認する必要に迫られたため証明した。おまけで最遠点対の総数を求めるのアルゴリズムを発見したので書いておいた。