読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

ポテンシャル解析

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

経路圧縮のみを用いた 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

Educational Codeforces Round 6 の F 問題 Xors on Segments の想定解が Mo's algorithm らしいのですが、Mo's algorithm を知らなかったので調べました。 そのついでに記事にしておきます。 このページを参考にしました。 www.hackerearth.com 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分解で解ける問題を最近よく見る。(想定解法であるかどうかは別として)No.235 めぐるはめぐる (5) - yukicoder F: 根付き木のみさわさん - 天下一プログラマーコンテスト2015本戦(オープンコンテスト) | AtCoder Problem - 588E - Codeforces Problem …

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

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