1. 概要 本記事では，中国剰余定理（Chinese Remainder Theorem, CRT）について解説します．中国剰余定理は，どの $2$ つも互いに素であるような正整数 $m_0,m_1,\ldots,m_{n-1}$ に対して，合同式 $$ x\equiv a _ 0\pmod{m _ 0},\quad x\equiv a _ 1\pmod{m…

解説動画はこちらです． 1. 概要 Undirected Vertex Geography は，無向グラフ上で駒を動かす $2$ 人ゲームです．各手番では，現在駒がある頂点から隣接する頂点に駒を移動させます．ただし，選べる頂点は，一度も駒が置かれたことがない頂点に限ります．動…

2026/06/19 解説記事 線形漸化式の復元 を公開しました． 2026/06/12 解説動画 オイラーツアーテクニック の解説動画を公開しました． 重軽分解（HLD） の解説動画を公開しました． 更新 Bostan–Mori のアルゴリズム（発展） の 3.8 節，4.3 節に補足説明を…

年別 2026 年 最近の更新 2026/06/19 解説記事 線形漸化式の復元 を公開しました． 2026/06/12 解説動画 オイラーツアーテクニック の解説動画を公開しました． 重軽分解（HLD） の解説動画を公開しました． 更新 Bostan–Mori のアルゴリズム（発展） の 3.8…

AtCoder では，競技プログラミングにおけるさまざまな理論やテクニックを解説する講座シリーズ「AtCoder Algorithm Lectures」を始めることになりました． 講座の内容について 講座では，競技プログラミングやその周辺の理論・テクニックを解説します．初心…

1. 概要 アッカーマン関数はある漸化式によって定義される $2$ 変数関数で，極端に速く増加するという特徴があります．競技プログラミングでは，その逆関数のようなものである逆アッカーマン関数が，Union-Find や静的なモノイド列の区間積クエリの計算量評…

1. 概要 本記事では，競技プログラミング（あるいは AtCoder Algorithm Lectures）での使用頻度が高い，代数構造に関する用語および，その代表例について解説します． 代数構造は典型的には，集合と集合上の演算の組として定義されます．例えば，整数に対す…

解説動画はこちらです． 1. 概要 この記事は，競技プログラミングの問題文や解説，AtCoder Algorithm Lectures の解説で頻出の用語や記号を，特に多くの分野に共通するものについて，簡単にまとめたものです． 特定の分野やアルゴリズムに特有の用語や記号に…

AND 畳み込み（1） Berge の定理（1） Berlekamp–Massey のアルゴリズム（1） Binary Trie（2） Bostan–Mori のアルゴリズム（2） Bézout の等式（1） C-recursive（4） Catalan 数（1） Color Coding（1） Cycle Lemma（1） Dilworth の定理（1） Disjoint …

1. 概要 本記事では，Color-Coding という手法について解説します． Color-Coding とは $k$ 個のものを選ぶというような存在判定問題や最適化問題において，それぞれのものにランダムな色を割り当てるという手法です．特に，比較的小さな $k$ について「ちょ…

解説動画はこちらです． 1. 概要 無向単純グラフに対して，同じ頂点に接続する $2$ 辺が同じ色を持たないように，辺に色を割り当てることを辺彩色（edge coloring）といいます．辺彩色に必要な色数の最小値をそのグラフの辺彩色数（edge-chromatic number，c…

解説動画はこちらです． 1. 概要 本記事では，数え上げに関する Cycle Lemma と呼ばれる定理を紹介します． これはある種の整数列について，列の巡回シフトのうち，累積和が常に正になるものの個数を決定するもので，主張も証明も易しいです．本記事では Cyc…

1. 概要 単純無向グラフにおいて，各頂点の次数を並べてできる列 $d = (\deg(1),\deg(2),\ldots,\deg(n))$ を次数列といいます． 本記事では，$d=(d_1,d_2,\ldots,d_n)$ が単純無向グラフの次数列となるための必要十分条件を与える $\text{Erd\H{o}s--Gallai…

1. 概要 本記事では，静的な列に対する区間クエリを高速に処理するデータ構造である Disjoint Sparse Table （DST と略記することもあります）を解説します． Disjoint Sparse Table は，長さ $N$ の列に対して事前計算 $\mathrm{O}(N\log N)$ 時間を行うこ…

1. 概要 本記事では長さ $2 ^ N$ の列の XOR 畳み込みを求める問題を扱います． この問題は，整数列や実数列を対象とするような通常の状況では，Walsh-Hadamard 変換を用いて $\mathrm{O}(N\cdot 2 ^ N)$ 時間で求めることができます． Walsh-Hadamard 変換…

1. 概要 本記事では，ある種の dp を高速化するテクニックについて解説します． 線形代数を学んだことがある方は，固有値・固有ベクトルあるいは行列の対角化によって行列の $M$ 乗計算を高速化する手法を見たことがあるかもしれません．本記事の内容は，同…

解説動画はこちらです． 1. 概要 本記事では，Euclid の互除法（Euclidean Algorithm）について解説します． Euclid の互除法は 2 つの整数の最大公約数（gcd）を求めるアルゴリズムとして有名です．しかし，その応用は最大公約数を求めることだけに留まりま…

解説動画はこちらです． 1. 概要 本記事では，オイラーツアーテクニック について解説します． オイラーツアーテクニックは 論文 3 において導入されたテクニックです．これは木の情報を，頂点全体や辺全体を特定の方法で $1$ 列に並べることによって表現す…

1. 概要 正整数の $0$ 乗和， $1$ 乗和， $2$ 乗和， $3$ 乗和について $$ \begin{aligned} \sum _ {n = 1} ^ N n ^ 0 &= N,\\ \sum _ {n = 1} ^ N n ^ 1 &= \frac12 N(N+1) = \frac12 N ^ 2 + \frac12 N,\\ \sum _ {n = 1} ^ N n ^ 2 &= \frac16 N(N+1)(2N+…

1. 概要 本記事では，グラフに関する用語について整理します． グラフ理論は数学分野の中でも，同じ用語が文献によって少し違った意味で使われているといったことが特に多く見られる分野です．本記事ではその中でも標準的と思われる定義を採用し，定義揺れが…

解説動画はこちらです． 1. 概要 本記事では，根付き木の HLD（重軽分解）について解説します． HLD は根付き木の辺を heavy edge，light edge の $2$ 種に分けて扱うことで，木の頂点全体をいくつかのパスに分解するものです． HLD は，木に対するさまざま…

AtCoder では，競技プログラミングにおけるさまざまな理論やテクニックを解説する講座シリーズ「AtCoder Algorithm Lectures」を始めることになりました． AtCoder Algorithm Lectures とは AtCoder Algorithm Lectures 更新履歴 カテゴリ一覧 Discord サー…

1. 概要 根付き木における $2$ 頂点 $u, v$ に対して， $u$ から $v$ へのパスが通る，深さ最小の頂点を $u,v$ の LCA といい， $\mathrm{LCA}(u,v)$ と書きます． LCA の計算については，オイラーツアーテクニック などでも触れました．本記事ではそれより…

解説動画はこちらです． 1. 概要 $2$ つの整数列（または実数列）$A = (A _ 0, A _ 1, \ldots, A _ {N})$, $B = (B _ 0, B _ 1, \ldots, B _ {M})$ に対して， $C _ k = \min _ {i + j = k}(A _ i + B _ j)$ により定義される列 $C = (C _ 0, \ldots, C _ {N…

解説動画はこちらです． 1. 概要 本記事では合同式の基礎的な考え方について説明します． 合同式は，整数全体を $m$ で割ったときの余り（剰余）に応じて分類するものです．競技プログラミングでは特に「答えを $m$ で割った余りで出力せよ」という形式が頻…

1. 概要 本記事では，parking function（駐車関数）と呼ばれる数列の個数を数え上げる問題を解説します． Parking function はハッシュテーブルの研究などに関連して現れた組合せ論的対象です．またその呼称の通り，駐車場に車を停めるというユニークな問題…

1. 概要 通常のセグメント木は，更新を行うたびに古い状態を破棄し，常に最新のバージョンだけを保持する構造になっています．それに対して 永続セグメント木 は，過去のすべてのバージョンに対してアクセスや更新が可能なセグメント木です． 永続セグメント…

1. 概要 本記事では，$\mathbb{F}_p$ 係数の多項式に関する重要事項について解説します． 議論の大部分は，多項式について中学・高校の数学で学んだ内容の再確認になると思います．ただし，中学・高校の数学では，多項式の係数として主に実数（や複素数）を…

1. 概要 本記事では，素数の基礎的な性質について解説します． $2$ 以上の整数 $p$ のうちで，$1,p$ 以外に約数を持たないものを素数ということはよく知られていると思います．非自明な約数がないというのが素数の定義ですが，「$ab$ が $p$ の倍数ならば $a…

解説動画はこちらです． 1. 概要 競技プログラミングの学習をしていると，次のような結果を目にすることがあると思います． $N$ 以下の素数の個数は $\displaystyle \frac{N}{\log N}$ 程度である（素数定理）． $N$ 以下の素数の逆数の総和 $\displaystyle …

1. 概要 本記事では，素数を法とする原始根について解説します．特に原始根の存在の証明を主な目標とします． これは $p$ を素数とするとき，$\mathbb{F}_p$ の元のうち $0$ でないもの全体が（あるいは $p$ を法として $1$ 以上 $p-1$ 以下の整数全体が）等…

解説動画はこちらです． 1. 概要 競技プログラミングにおいて，バグを起こさずに素早く正確に実装するというのは非常に重要なスキルです．一方で，バグを全く起こさないというのは上級者にとっても現実的ではありません．したがって，バグを起こしてしまった…

解説動画はこちらです． 1. 概要 本記事では，静的な配列に対するある種の区間クエリを高速に処理するデータ構造であるスパーステーブル（Sparse Table）を解説します． スパーステーブルは，事前計算に $\mathrm{O}(N\log N)$ 時間を使うことで，区間最小値…

1. 概要 本記事では，Sqrt Tree について解説します． Sqrt Tree は列の平方分割を再帰的に行うことでできる木構造です．特に静的なモノイド列に対する区間積クエリを高速に処理できます．具体的には，列の長さを $N$ とするとき，事前計算 $\mathrm{O}(N\lo…

1. 概要 本記事では Sqrt Tree などに続き，再び静的なモノイド列に対する区間積クエリの問題を扱います． 特に，長さ $N$ の列について $\mathrm{O}(N)$ 時間の事前計算を前提とした場合，クエリあたり $\mathrm{O}(\alpha(N))$ 時間（$\alpha(N)$ は逆アッ…

1. 概要 本記事では，部分集合・上位集合関係に関するゼータ変換，メビウス変換について解説します．ゼータ変換・メビウス変換はより一般に順序集合に対して定義されるものですが，本記事で扱うのはその特殊ケースということになります． 2. 前提知識 $\lbra…

解説動画はこちらです． 1. 概要 任意の相異なる $2$ 頂点 $u,v$ について，$u\to v$ または $v\to u$ のどちらか一方が必ず存在するような単純有向グラフをトーナメントといいます．これは $N$ 人が総当たり戦をしたときの勝敗を，「勝った人から負けた人へ…

1. 概要 転置原理は，ある問題の解法から別の問題（転置問題）の解法を機械的に導出するという，意外性のある面白い考え方です． 特に多項式の多点評価のアルゴリズムの定数倍高速化が転置原理を通して発見されたことが有名です．他には形式的べき級数の合成…

1. 概要 本記事では，Union-Find の計算量が $\mathrm{O}\left(N+Q\alpha(N)\right)$ であるという事実を証明します． この事実は競技プログラミングユーザーの多くが知っている非常に有名なものだと思いますが，Union-Find の基礎的な動作原理や，計算量 $\…

解説動画はこちらです． 1. 概要 Wavelet Matrix の基礎的な理解や実装方法については， Wavelet Matrix（基礎） で解説しました． 本記事では改めて，Wavelet Matrix を使うとどのような処理をできるのかについて，具体的な例をいくつか確認します． なおほ…

解説動画はこちらです． 1. 概要 本記事では，Wavelet Matrix というデータ構造について解説します。 Wavelet Matrix とは大雑把に言えば，静的な非負整数列 $A=(A_0,A_1,\ldots,A_{N-1})$ に対して，クエリ $(L,R)$ が与えられるたびに，「多重集合 $\lbrac…