コンテンツにスキップ

講座

タグ「講座」の記事 20 件

多角形のモーメントとは何か

shogo-library の多角形のライブラリには、PolygonMoment という型と polygon_edge_moment という関数があります。どちらも「面積と一次モーメント」を扱うものですが、モーメントという言葉はなじみが薄いと思います。この記事では、モーメントとは何か、なぜ重心を求めるのに便利なのか、ライブラリでは何ができるのかを説明します。

数直線上に、重さ m1,m2,…,mnm_1, m_2, \dots, m_n のおもりが位置 x1,x2,…,xnx_1, x_2, \dots, x_n に置かれているとします。このとき

  • 零次モーメント:M0=∑imiM_0 = \sum_i m_i(重さの合計)
  • 一次モーメント:M1=∑imixiM_1 = \sum_i m_i x_i(重さ × 位置の合計)
  • 二次モーメント:M2=∑imixi2M_2 = \sum_i m_i x_i^2(重さ × 位置の 2 乗の合計)

をモーメントと呼びます。kk 次モーメントは「重さ × 位置の kk 乗」の合計です。

重心(重さの平均位置)は g=M1/M0g = M_1 / M_0 です。一次モーメントを零次モーメントで割ると重心になる、というのがこの記事でいちばん大事な式です。

名前の由来はてこです。位置 cc を支点にすると、おもり ii が回そうとする強さ(力のモーメント)は mi(xi−c)m_i (x_i - c) で、合計は M1−cM0M_1 - c M_0 です。これが 00 になる、つまり釣り合う支点が c=M1/M0c = M_1 / M_0、すなわち重心です。

平面の図形 DD では、おもりの代わりに面積を重さと考え、和を積分に置き換えます。

S=∬D1 dA,Mx=∬Dx dA,My=∬Dy dAS = \iint_D 1 \, dA, \qquad M_x = \iint_D x \, dA, \qquad M_y = \iint_D y \, dA

SS は面積(零次モーメント)、(Mx,My)(M_x, M_y) は一次モーメントです。図形の重心は

(gx,gy)=(MxS,MyS)(g_x, g_y) = \left( \frac{M_x}{S}, \frac{M_y}{S} \right)

です。言いかえると、一次モーメントは「面積 × 重心」です:(Mx,My)=S⋅(gx,gy)(M_x, M_y) = S \cdot (g_x, g_y)。

モーメントは足せる、重心は足せない

Section titled “モーメントは足せる、重心は足せない”

モーメントが便利なのは、図形を分割したとき、各部分のモーメントを足すと全体のモーメントになることです。積分の範囲を分けているだけなので当然です。面積が足せるのと同じ理由で、一次モーメントも足せます。

一方、重心はそのままでは足せません。図形 AA と BB をくっつけた図形の重心は、AA の重心と BB の重心の平均ではなく、面積で重みを付けた平均

g=SAgA+SBgBSA+SBg = \frac{S_A g_A + S_B g_B}{S_A + S_B}

です。分子は一次モーメントの和、分母は面積の和なので、これは「モーメントを足してから割る」と言っているだけです。

例として、L 字形の図形 (0,0),(2,0),(2,1),(1,1),(1,2),(0,2)(0,0), (2,0), (2,1), (1,1), (1,2), (0,2) の重心を求めます。

  • 下の長方形 [0,2]×[0,1][0,2] \times [0,1]:S=2S = 2、重心 (1,0.5)(1, 0.5)、一次モーメント (2,1)(2, 1)
  • 左上の長方形 [0,1]×[1,2][0,1] \times [1,2]:S=1S = 1、重心 (0.5,1.5)(0.5, 1.5)、一次モーメント (0.5,1.5)(0.5, 1.5)

足すと S=3S = 3、一次モーメント (2.5,2.5)(2.5, 2.5) なので、重心は (2.5/3,2.5/3)=(5/6,5/6)(2.5/3, 2.5/3) = (5/6, 5/6) です。

引き算もできます。穴の開いた図形のモーメントは「外側のモーメント − 穴のモーメント」です。このように足し算と引き算ができることが、あとで累積和に載せるときに効いてきます。

多角形のモーメントを辺ごとに分解する

Section titled “多角形のモーメントを辺ごとに分解する”

三角形 a,b,ca, b, c の面積は外積で S=12(b−a)×(c−a)S = \frac{1}{2} (b - a) \times (c - a)、重心は 3 頂点の平均 a+b+c3\frac{a + b + c}{3} です。したがって一次モーメントは

S⋅a+b+c3S \cdot \frac{a + b + c}{3}

です。

原点を頂点にした三角形に分ける

Section titled “原点を頂点にした三角形に分ける”

反時計回りの多角形 p0,p1,…,pn−1p_0, p_1, \dots, p_{n-1} を、辺 pi→pi+1p_i \to p_{i+1} ごとに原点 OO と結んだ三角形 O,pi,pi+1O, p_i, p_{i+1} に分けます(pn=p0p_n = p_0)。この三角形の符号付き面積は 12 pi×pi+1\frac{1}{2} \, p_i \times p_{i+1} で、OO から見て反時計回りなら正、時計回りなら負です。

O p₀ p₁ p₂ p₃
青は正(反時計回り)の三角形、赤は負(時計回り)の三角形。太線が多角形。

図では Op0p1O p_0 p_1, Op1p2O p_1 p_2, Op2p3O p_2 p_3 の 3 つが正で、これらを合わせると多角形よりはみ出します。はみ出した部分はちょうど負の三角形 Op3p0O p_3 p_0 と重なり、打ち消されます。凹多角形でも、原点が多角形の外にあっても同じことが起き、各点は「多角形の内部なら合計 1 回、外部なら合計 0 回」数えられます(正確には、その点のまわりを多角形が何周するか、つまり回転数の回数だけ数えられます)。

面積だけでなく一次モーメントも積分なので、同じように符号付きで足せば打ち消し合いが起きます。三角形 O,pi,pi+1O, p_i, p_{i+1} の重心は pi+pi+13\frac{p_i + p_{i+1}}{3} なので、多角形全体は

S=12∑ipi×pi+1,(Mx,My)=16∑i(pi×pi+1)(pi+pi+1)S = \frac{1}{2} \sum_i p_i \times p_{i+1}, \qquad (M_x, M_y) = \frac{1}{6} \sum_i (p_i \times p_{i+1}) (p_i + p_{i+1})

となります。面積の式は、よく知られた外積で多角形の面積を求める式(靴ひも公式)そのものです。一次モーメントの式はそれを一歩進めたものです。

polygon_edge_moment(p, q) は、辺 p→qp \to q の寄与(三角形 O,p,qO, p, q の符号付き面積と一次モーメント)を返します。分母の 2 と 6 を払った値を持っているので、整数座標なら誤差なく計算できます。

メンバ中身式
area2面積の 2 倍p×qp \times q
mxxx の一次モーメントの 6 倍(p×q)(px+qx)(p \times q)(p_x + q_x)
myyy の一次モーメントの 6 倍(p×q)(py+qy)(p \times q)(p_y + q_y)

全辺の寄与を足すと、多角形全体の PolygonMoment になります。area() は area2 / 2、centroid() は

gx=MxS=mx/6area2/2=mx3⋅area2g_x = \frac{M_x}{S} = \frac{\texttt{mx} / 6}{\texttt{area2} / 2} = \frac{\texttt{mx}}{3 \cdot \texttt{area2}}

を計算しています(gyg_y も同様)。polygon_centroid は、これを全辺について足して重心を返すだけの関数です。

さきほどの L 字形で確かめると、辺ごとの (area2, mx, my) は

辺area2mxmy
(0,0)→(2,0)(0,0) \to (2,0)000
(2,0)→(2,1)(2,0) \to (2,1)282
(2,1)→(1,1)(2,1) \to (1,1)132
(1,1)→(1,2)(1,1) \to (1,2)123
(1,2)→(0,2)(1,2) \to (0,2)228
(0,2)→(0,0)(0,2) \to (0,0)000
合計61515

で、面積 6/2=36/2 = 3、重心 15/(3⋅6)=5/615 / (3 \cdot 6) = 5/6 と、長方形に分けて求めた結果と一致します。

座標が 10910^9 程度だと mx は 102710^{27} 程度になるので、整数座標のときは __int128_t で値を持ちます。

部分多角形の面積と重心を O(1)O(1) で求める

Section titled “部分多角形の面積と重心を O(1)O(1)O(1) で求める”

いちばんの使いみちです。多角形の頂点 u,u+1,…,vu, u+1, \dots, v を順に結んで閉じた部分多角形の面積や重心を、たくさん求めたいとします。

部分多角形の辺は、元の多角形の辺 u→u+1,…,v−1→vu \to u+1, \dots, v-1 \to v と、閉じる辺 v→uv \to u です。モーメントは辺ごとの寄与の和なので、前者は寄与の累積和で O(1)O(1) で求まり、そこに閉じる辺の寄与を 1 つ足せば完成です。PolygonMoment は + と - が使えるので、そのまま累積和に載せられます。頂点の番号が一周をまたぐ場合もあるので、円環上の区間和 CircularSum を使うと便利です。

using P = Vector<long long>;
std::vector<PolygonMoment<long long>> e(n);
for (int i = 0; i < n; i++) e[i] = polygon_edge_moment(ps[i], ps[(i + 1) % n]);
CircularSum cs(e);
// 頂点 u, u+1, ..., v を結んだ部分多角形
auto m = cs.sum(u, v) + polygon_edge_moment(ps[v], ps[u]);
m.area(); // 符号付き面積
m.centroid(); // 重心

辺の寄与は原点の位置によって変わりますが、閉じた多角形について足した合計は原点によりません(打ち消し合いの議論は原点の位置を問わないからです)。途中までの和だけでは意味のある値にならず、閉じる辺を足して初めて部分多角形の値になる、という点に注意してください。

凸多角形を対角線で 2 つに切ったときの面積の差を最小化する、といった問題では、切り方ごとに両側の面積が O(1)O(1) で求まるので、尺取り法や二分探索と組み合わせられます。重心が要る問題でも同じように扱えます。

頂点 pip_i を動かすと、寄与が変わるのは辺 pi−1→pip_{i-1} \to p_i と pi→pi+1p_i \to p_{i+1} の 2 つだけです。PolygonMoment の和は結合的なので、セグメント木に載せれば、頂点の更新と部分多角形のモーメントの取得がそれぞれ O(log⁡n)O(\log n) でできます。

離れた複数の多角形をまとめた図形の重心は、それぞれの PolygonMoment を足してから centroid() を呼べば求まります。穴の開いた図形は、外側から穴を引きます。時計回りの多角形の寄与は符号が反転するので、穴を時計回りで与えれば、外側と穴の寄与をすべて足すだけでも同じ結果になります。

整数座標なら area2, mx, my はすべて整数で、重心は gx=mx/(3⋅area2)g_x = \texttt{mx} / (3 \cdot \texttt{area2}) という分数です。2 つの図形の重心の xx 座標の大小や、重心がある点と一致するかどうかは、分母を払って整数のまま比べられます(分母の符号に注意してください)。centroid() は double を返すので、厳密な判定が必要なときはメンバを直接使います。

ライブラリにはありませんが、同じ考え方で二次モーメントも辺ごとに分解できます。

Ixx=∬Dx2 dA=112∑i(pi×pi+1)(xi2+xixi+1+xi+12)I_{xx} = \iint_D x^2 \, dA = \frac{1}{12} \sum_i (p_i \times p_{i+1}) (x_i^2 + x_i x_{i+1} + x_{i+1}^2)

(xix_i は pip_i の xx 座標。IyyI_{yy} も同様)。L 字形で計算すると Ixx=3I_{xx} = 3 になり、長方形ごとに積分した 83+13\frac{8}{3} + \frac{1}{3} と一致します。

二次モーメントがあると、たとえば図形内の一様ランダムな点と点 cc の距離の 2 乗の期待値が

Ixx+IyyS−2 c⋅g+∣c∣2\frac{I_{xx} + I_{yy}}{S} - 2 \, c \cdot g + |c|^2

で求まります。物理でいう慣性モーメント(回転させにくさ)も、この Ixx+IyyI_{xx} + I_{yy} です。

  • kk 次モーメントは「重さ × 位置の kk 乗」の合計で、図形なら積分。零次は面積、一次は「面積 × 重心」
  • モーメントは図形を分割すると足し算・引き算できるが、重心はそのままでは足せない。だからモーメントで持って、最後に割る
  • 多角形は原点と各辺の三角形に符号付きで分けられるので、モーメントは辺ごとの寄与の和になる
  • 寄与の累積和を取れば、部分多角形の面積と重心が O(1)O(1) で求まる。PolygonMoment はそのための型

尺取り法のリンク集

尺取り法(しゃくとり法)について、参考になる記事や資料をまとめました。

尺取り法は、数列の区間 [l,r)[l, r) の左端と右端をどちらも右にだけ動かしながら、条件を満たす区間を調べる手法です。「区間が条件を満たすなら、それに含まれる区間も満たす」(または「それを含む区間も満たす」)という単調性があると、左端 ll ごとの右端の境目が ll について単調になります。そのため、右端を伸ばせるだけ伸ばし、次に左端を 1 つ縮める、を繰り返すと、全体で O(N)O(N) 回の操作で済みます。条件を満たす区間の最大長・最小長・個数を求めるときによく使われます。

区間の和で判定するときは、値が非負(正)であることが単調性の前提です。負の値があると使えないので、累積和と二分探索やデータ構造を組み合わせる方法を考えます。また、ソートした配列の両端から 2 本のポインタを寄せていく方法も、two pointers と呼ばれます。

  • しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ(drken、Qiita)
    • 尺取り法が使える場面を「条件を満たす区間の最小長・最大長・個数」の 3 つに整理し、AOJ DSL_3_C を例に、素朴な O(n2)O(n^2) の方法から「右端の境目が左端について広義単調増加」という観察を経て O(n)O(n) にするまでを、図と C++ のコードで説明しています。使える条件、二分探索との類似、スライド最小値や Convex Hull Trick との関係まで扱い、最後に AtCoder などの問題例が並んでいます。
    • 細かい誤記がいくつかあります。たとえば最後の問題「L番目のK番目の数」の出典が、冒頭では JOI 2017 予選 E、本文では予選 F となっています(AtCoder 上では JOI 2018 予選 F)。また、ABC098 D の問題概要は「正の整数列」とありますが、実際は 00 も含みます。
  • 競プロ典型 90 問 034 の解説(E869120、画像)
    • 値の種類が KK 以下の最長の区間を求める問題を例に、左端 ii ごとの右端の限界 cic_i を表にし、c1≤c2≤⋯c_1 \le c_2 \le \cdots という単調性から操作が合計 2N2N 回で済むことを 1 枚で説明しています。C++ の解答コードと、類題の一覧もあります。
  • しゃくとり法のDequeを使ったバグりにくい実装(keroru、Qiita)
    • 添字を動かす代わりに、右端の要素を deque に入れ、条件を満たさない間は先頭から取り出す実装を、ABC032 C を例に Python で説明しています。deque の中身の推移をデバッグ出力で見せ、一般形のテンプレートも載せています。単調性の説明はないので、上の記事とあわせて読んでください。
  • 尺取り法の実装で嵌ったあの日の涙を数え切れないあなたにお送りする、尺取り法実装の † ソウル † です。(ngtkana、Qiita)
    • 尺取り法の難しさを「左右の端を動かしたときの状態の更新」と「どう動かすか」に分けて、和が KK 以下・KK より大きい区間の数え上げ、最大長・最小長などを C# で書き分けています。要素が 00 以上であることを「大事な仮定」として明示しています。図はありません。
    • コードにそのままでは誤答になる誤りがあります。和が KK 以下の区間を数えるコードで、左端を進めるときに sum += a[l++] となっている箇所(正しくは -=)、最小長のコードで ans を 00 で初期化したまま Math.Min を取っている箇所などです。
  • 二分探索のリンク集:左端ごとの右端の境目は、累積和の上の二分探索でも求められます。尺取り法より log⁡\log が付きますが、考えやすいこともあります。
  • 累積和・いもす法のリンク集:区間の和の判定や、区間内の特定の要素の個数を O(1)O(1) で求めるのに使います。
  • スライド最小値のリンク集:両端が単調に動く区間の最小値・最大値を deque で求める手法で、尺取り法と組み合わせてよく使われます。

尺取り法を扱う講座はまだありません。競技プログラミング基本用語集の 6.2「区間」(半開区間の表記)、6.3「部分列,部分配列(連続部分列)」、6.6「単調性」の節で、関連する用語を確認できます。

日本語版・英語版の Wikipedia には、尺取り法(two pointers)の記事はありません。

  • Two Pointers(USACO Guide)
    • 両端から寄せる型(ソートした配列で和が xx になる 2 要素を探す CSES Sum of Two Values)と、同じ向きに動かす型(Codeforces 279B Books)を、表やアニメーションで説明しています。C++・Java・Python のコードと、12 問の問題一覧があります。
    • 末尾の小テストは、two pointers を「2 つの添字の組を探す手法」とする選択肢だけを正解にしていて、本文の同じ向きに動かす型と噛み合いません。
  • Competitive Programmer’s Handbook(Antti Laaksonen、PDF)
    • 8 章「Amortized analysis」の 8.1 節「Two pointers method」で、正の整数の列で和がちょうど xx の区間を探す問題と、2SUM(和が xx になる 2 要素)を図で説明しています。コードはありません。8.3 節はスライド最小値です。
  • Two Pointers Method(Codeforces EDU)
    • ITMO Academy の講座の 1 レッスンです。中身を見るには Codeforces へのログインが必要です。

左端を 1 つ進めるたびに右端を伸ばせるだけ伸ばす、という基本の形の問題です。

ソートした配列の上で 2 本のポインタを動かす形の問題です。

  • ABC481 E - Most Brilliant Starry Sky
    • 星を偏角の順に並べ、偏角に 2π2\pi を足した写しを後ろにつなげた列の上で、偏角の幅が π\pi 未満の区間を尺取り法で求めています。円環の上の尺取り法の例です。

座標圧縮のリンク集

座標圧縮について、参考になる記事や資料をまとめました。

座標圧縮(座圧)は、値を「全体の中で何番目に小さいか」に置き換える手法です。値の大小関係だけが大事で、値そのものが 10910^9 のように大きいときに、00 から N−1N - 1 までの添字に直して配列で扱えるようにします。同じ値には同じ番号を付けます。

C++ では、値をコピーしてソートし、std::unique と erase で重複を除いたあと、std::lower_bound で各値の番号を求めます。Python では sorted(set(A)) で重複のない昇順の列を作り、辞書で値から番号を引くか、bisect_left で番号を求めます。どちらも計算量は O(Nlog⁡N)O(N \log N) です。

よく使うのは、次のような場面です。

  • データ構造に載せる:値を添字にして BIT やセグメント木に載せるとき、値を圧縮して大きさを O(N)O(N) に抑えます。後から来るクエリの値も含めて圧縮するため、クエリを先読みすることが多いです。転倒数を求めるときも、値が大きければまず圧縮します。
  • 区間を扱う:区間の端点だけを集めて圧縮すると、数直線が「端点から次の端点まで」の小区間の並びになり、どの区間も小区間をいくつか並べたものになります。区間を半開区間 [l,r)[l, r) で表して端点 l,rl, r を集めると、扱いが簡単です。閉区間 [l,r][l, r] なら ll と r+1r + 1 を集めます。小区間の長さは、圧縮前の値の差で求めます。いもす法と組み合わせることもよくあります。
  • 2 次元のグリッド:x 座標と y 座標をそれぞれ別に圧縮して、小さなグリッドに直します。長方形や線分で区切られた領域を扱うときは、端点だけを残すと隙間が消えてしまうことがあり、端点の隣の座標も残す必要があります。
  • 座標圧縮 (座圧)(けんちょんの競プロ精進記録)
    • 「全体の中で何番目に小さいか」という定義から始めて、C++(ソート、unique と erase、lower_bound)と Python(sorted(set(A)) と辞書)の実装、例題の ABC036 C と ABC113 C、発展として 2 次元の点の座標圧縮(ABC213 C)を説明しています。初心者向けです。
  • 座標圧縮の解説(1次元から2次元の圧縮まで)(アルゴリズムロジック)
    • 1 次元の座標圧縮の手順と C++ の実装から、線分や長方形を扱う 2 次元の座標圧縮に進みます。端点だけでなく「一つ隣」の座標も残さないと隙間が消えてしまう理由を、圧縮の前後の図で説明しているのが特徴です。例題は AOJ DSL_4_A(長方形の面積の和)で、座標圧縮と 2 次元のいもす法で解いています。練習問題の一覧もあります。
    • 2.4 節のコードは for (T d = 0; d < 1; d++) になっていて、d = 0 しか回らないので、説明している「一つ隣の座標」が追加されません。最後の DSL_4_A のコードのように d <= 1 にしてください。
  • 座標圧縮(北海道大学 HCPC、PDF)
    • 2017 年の勉強会のスライドです。1 次元(ABC036 C)のあと、蟻本の「領域の個数」を例に、線分の端点だけを残すと誤る例を示して、端点の隣に余白の座標を足す方法を図で説明しています。応用として AOJ 2426 Treasure Hunt(座標圧縮と 2 次元の累積和)も扱っています。
    • スライドにコードはなく、GitHub へのリンクは切れています。コードは今はこちらにあります。スライド自身に、コードは verify していないと書かれています。
  • 座標圧縮に関する解説と練習問題(Baby Stepsなブログ)
    • 端点とその隣の座標を登録する圧縮の関数と、それを使った 3 問の C++ の解答です。AOJ DSL_4_A(2 次元のいもす法)、JOI 2008 本選「ペンキの色」(領域の個数を BFS で数える)、JOI 2013 予選「魚の生息範囲」(3 次元)を扱っています。説明は短く、コードが中心です。
  • 座標圧縮について勉強した java(バイトの競プロメモ)
    • 壁で区切られたグリッドを、まず x 方向だけ圧縮する様子を図で示しています。長方形の右端を半開区間の端として持てば、端点だけを残しても領域が小区間の並びとして正しく残ることが、具体的な数で分かります。両端の座標を入れ忘れると外側の余白が消えることにも触れています。コードは Java の断片です。
  • 転倒数を Binary Indexed Tree(BIT)で求める(embermaverick05、Qiita)
    • 転倒数を BIT で求める入門記事で、最後に値が 10910^9 まである場合に、sorted(set(A)) から作った辞書で値を圧縮してから BIT に載せる方法を説明しています。コードは Python です。
  • 平面走査について(Shirotsume、Qiita)
    • 転倒数を例に、片方の座標の順に処理しながら、もう片方の座標を BIT で数える平面走査の考え方を一般化して説明しています。座標圧縮そのものの解説ではありませんが、クエリを先読みして圧縮し、データ構造に載せるオフライン処理の考え方が分かります。コードはなく、数式と文章で説明しています。

AtCoder Library(ACL)に座標圧縮の機能はありません。

  • std::unique(cpprefjp)
    • std::unique は隣り合う重複を除いた要素を先頭に集めるだけで、要素数は減らないこと、実際に消すには戻り値を使って erase する必要があることが書かれています。隣り合う重複しか消さないので、先にソートが必要なことも例で分かります。
  • misc/compress.hpp(Nyaan’s Library)
    • 座標圧縮の構造体の C++ の実装です。説明の文章はなく、コードだけのページです。値の番号を求める get(x) は、x が登録されていなくても「xx 以上の最初の位置」を返すので、区間の端を求めるのにも使えます。
  • other/compress.hpp(Luzhiled’s Library)
    • 値を add で登録してから build で整える形の C++ の実装で、こちらもコードだけのページです。コンストラクタで値を渡しても build は呼ばれないので、番号を求める前に必ず build を呼んでください。

座標圧縮そのものを扱う講座はありませんが、座標圧縮を使う講座があります。

  • Wavelet Matrix(発展)
    • 6 章「2 次元点群に対する矩形処理」で、点の座標を圧縮して 00 から N−1N - 1 に直してから Wavelet Matrix に載せています。点の追加・削除がある問題では、クエリをすべて先読みしてから座標圧縮する方法も説明しています。難易度の高い講座です。
  • 区間クエリのためのモノイド設計
    • 8.1 節「転倒数」の補足で、値を添字にするときは座標圧縮してセグメント木の大きさを O(N)O(N) に抑えればよい、と触れています。

日本語版・英語版の Wikipedia と cp-algorithms には、座標圧縮の記事も節もありません。

  • Custom Comparators and Coordinate Compression(USACO Guide、英語)
    • 前半はソートの比較関数の話で、後半が座標圧縮です。2 次元の点の座標をソートした順位に置き換える例(USACO 2020 Dec Silver「Rectangular Pasture」)と、長さ 10910^9 の配列への区間加算と区間和を、端点を集めて圧縮し、圧縮前の値の差を小区間の長さとして使って解く例(Codeforces Gym 102951 D)があります。コードは C++・Java・Python から選べます。
    • 1 つ目の例のコードは、ソートした順に番号を振るだけで、重複を除いていません。この問題では座標がすべて異なることが保証されているので正しく動きますが、重複がある問題にそのまま使うと誤ります。
  • Spoj Problem: Election Posters(Codeforces、英語)
    • 区間を塗り重ねる問題についての質問スレッドです。端点だけを圧縮すると、間にある隙間が消えて答えが変わってしまう反例がコメントで示されていて、端点の扱いの落とし穴の実例になっています。
  • ABC188 D - Snuke Prime:料金が変わる日だけを取り出して(座標圧縮して)、いもす法で各期間の料金を求めます。
  • ABC221 D - Online games:ログイン人数が変わる日だけを取り出し、人数が同じ期間の日数を数えます。
  • ABC231 F - Jealous Two:片方の嬉しさの順に処理しながら、もう片方の嬉しさを圧縮して BIT で数えます。
  • AOJ DSL_4_A - Union of Rectangles:長方形の面積の和を、座標圧縮と 2 次元のいもす法で求めます。上のアルゴリズムロジックの記事が解説です。
  • ABC168 F - . (Single Dot):線分の端点で座標を圧縮してグリッドにし、牛のいる領域を BFS で探索して面積を足し合わせます。領域が外まで広がっていれば INF です。
  • SamCoding Round 7 (Div. 2) I - Subarrays in Range L-R
    • 最大 101410^{14} 程度になる累積和の値を座標圧縮し、BIT(セグメント木)で個数を数えています。
  • AALC001 J - Long Binary String
    • クエリを先読みして区間の端点を座標圧縮し、長さ 10910^9 の文字列を小区間の並びに直して、セグメント木で反転を処理しています。
  • AALC001 K - Multiset
    • クエリを先読みして現れる値を座標圧縮し、値ごとの情報をセグメント木で管理しています。

二分探索のリンク集

二分探索について、参考になる記事や資料をまとめました。

二分探索は、答えの候補が並んでいて、ある境目より手前では条件を満たさず、そこから先ではずっと満たす(単調性がある)ときに、その境目を O(log⁡N)O(\log N) 回の判定で求める手法です。ソート済みの配列から値を探すのが基本の形で、C++ の std::lower_bound や Python の bisect がこれにあたります。

競プロでよく使うのは、その一般化です。「答えを xx 以下にできるか」のような判定問題が xx について単調なら、答えそのものを二分探索で求められます(答えで二分探索)。最小値の最大化・最大値の最小化や、平均値の最大化がこの形の典型です。実数の範囲でも同じように探せますが、打ち切り方に注意が必要です。

実装では、条件を満たす側の端を ok、満たさない側の端を ng として、ok と ng が隣り合うまで真ん中で区切る書き方(めぐる式二分探索)がよく使われます。範囲が大きいときは、真ん中を (ok + ng) / 2 で計算すると和が型の範囲を超えることがあるので、ok + (ng - ok) / 2 のように書くと安全です。

セグメント木の上を降りながら境目を求める「セグメント木上の二分探索」については、セグメント木のリンク集も見てください。

  • 二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜(けんちょん、Qiita)
    • 値を探す素朴な二分探索から始めて、std::lower_bound の意味、「条件を満たす最小の xx を求める」形への一般化、ok と ng の 2 変数で大小の向きを気にせずに書くめぐる式、の順に説明しています。最後の例は年齢当てゲームです。コードは C++ です。
    • 最終形のコードは真ん中を (ok + ng) / 2 で計算しています。範囲が 101810^{18} 程度になる問題では、ok + (ng - ok) / 2 に直して使ってください。
    • 年齢当てゲームのコードのコメント「mid 歳以上 right 歳以下」は、本文の流儀(半開区間 [left,right)[\mathit{left}, \mathit{right}))では「right 歳未満」の誤りです。
  • 競プロ典型 90 問 001 - Yokan Party の解説(E869120、GitHub)
    • 「答えで二分探索」の入門です。「スコアを MM 以上にできるか」という判定問題に言い換え、それを貪欲法で O(N)O(N) で解いて、MM を二分探索します。「最小値の最大化」は答えで二分探索になることが多い、という指摘と類題もあります。解説は画像 1 枚で、C++ のサンプルコードは同じリポジトリの sol/001.cpp にあります。
  • 二分探索をはじめからていねいに(北海道大学 HCPC、PDF)
    • 2016 年の勉強会のスライドです。配列上の二分探索と lower_bound・upper_bound から始めて、実数の二分探索(回数を固定してループ)、最小値の最大化、最大値の最小化、平均値の最大化を、例題を 1 問ずつ解きながら説明しています。どれも蟻本の例題で、ジャッジは POJ です。コードは C++ で、画像なのでコピーはできません。
  • AtCoder ABC 034 D - 食塩水(けんちょんの競プロ精進記録)
    • 「濃度を xx % 以上にできるか」という判定問題に言い換え、式を変形して「(食塩の量) − (食塩水の量) × xx / 100 の大きいほうから KK 個の和が 00 以上か」で判定しています。実数の二分探索を 50 回のループで行う C++ のコードつきです。
  • 二分探索(Binary Search)のアルゴリズム(アルゴリズムロジック)
    • 値を探す二分探索、lower_bound、条件を満たす最小の位置を求める一般化、平均値の最大化(ABC034 D)を 1 ページで説明しています。Python と C++ のコードと、練習問題の一覧つきです。
    • 中級編の自作の my_lower_bound には誤りがあります。r を arr.size() - 1 から始めているので、xx がすべての要素より大きいときに arr.size() を返せません。また、x == arr[mid] で途中で返しているので、同じ値が複数あると左端を返しません。説明の「lower_bound 関数と upper_bound 関数」も、upper_bound は「xx より大きい値を持つ左端」なので正しくありません。
    • 食塩水のコードは while (ng - ok > 1e-10) で打ち切っています。この問題では止まりますが、値が大きい問題では止まらなくなることがあります(下の「実数の二分探索」を見てください)。
  • 実数の二分探索・三分探索はループ回数を決め打ちしようね(えびちゃんの日記)
    • while (hi - lo > eps) のように幅で打ち切ると、浮動小数点数で表せる値が飛び飛びなせいで止まらなくなる例を示し、ループの回数を決め打ちするよう勧めています。必要な回数の見積もり方(初めの幅を 101810^{18}、許される誤差を 10−910^{-9} とすると 90 回で足りる)と、三分探索の場合の回数も載っています。コードは C++ です。
  • 浮動小数点型で素朴に二分探索をして大丈夫?(えびちゃんの日記)
    • 上の記事の続きにあたる発展的な内容です。止まるかどうかだけでなく、判定関数の丸め誤差のせいで答えがずれる例を挙げて、結果が正しいかを議論しています。コードは Rust です。
  • Re: 浮動小数点数の二分探索(えびちゃんの日記)
    • double のビット列を大小関係を保つ 64 bit 整数に変換し、整数の二分探索として 64 回程度で済ませる方法です。例題は ABC026 D で、コードは Rust です。
    • 「C++ は bit_cast を C++20 まで待つ必要がある」とあるのは執筆当時の話で、今は C++20 で使えます。
  • 二分探索 二分法 違い(うさぎ小屋)
    • 「二分探索」と「二分法」という言葉の違いを整理した短い記事です。競プロで「にぶたん」と呼ぶものがどちらにあたるかも書いています。

複数の質問について、それぞれ「何番目の操作の時点で条件を満たすようになるか」を二分探索したいとき、全部の質問の二分探索を 1 段ずつまとめて進め、操作の列を各段で 1 回ずつ頭からたどる手法です。

  • CODE THANKS FESTIVAL 2017 H - Union Sets(並列二分探索解法)(ARMERIA)
    • 並列二分探索が使える問題の形、図を使った処理の流れ、各段で質問を mid ごとに振り分けて Union-Find の操作を頭からやり直す C++ の実装を説明しています。計算量の見積もりと、部分永続 Union-Find による別解の紹介もあります。
  • 並列二分探索(パラレルバイナリサーチ)(迷いませんか?)
    • SPOJ の Meteors と上の Union Sets を C++ で解いています。説明は短めで、著者自身が計算量の見積もりに自信がないと書いているので、上の記事の補助として読んでください。
  • Segtree(AtCoder Library のドキュメント)
    • max_right と min_left の仕様が載っています。返り値は「区間に ff を適用した結果が true から false に変わる境目」として定義されていて、ff が単調なら「true になる最大の rr」と読めます。計算量は O(log⁡N)O(\log N) です。仕様の説明だけで、セグメント木を降りる仕組みは書かれていません。
  • セグメント木上の二分探索のカテゴリ(けんちょんの競プロ精進記録)
    • セグメント木上の二分探索を使う問題の解説が並んでいて、問題集として使えます。
  • bisect --- 配列二分法アルゴリズム(Python 公式ドキュメント)
    • bisect_left・bisect_right・insort_left・insort_right の仕様と、ソート済みリストから「xx 未満の最大の要素」などを探すレシピがあります。key 引数は Python 3.10 で追加されたもので、それより古い環境では使えません。
    • 日本語訳が一部だけで、英語のまま残っている段落があります。レシピの find_ge のコメント「左端の項目がx以上であることを確認する」は、原文では「xx 以上の左端の項目を見つける」という意味です。
  • めぐる式二分探索 コピペで使えるPython実装(学習する天然ニューラルネット)
    • 判定関数 is_ok と ok・ng を渡すめぐる式二分探索の Python のテンプレートと、ABC146 C などでの使用例です。仕組みの説明は、けんちょんさんの記事などに任せています。
    • 「配列にできない関数を探索できる(bisect モジュールでは不可)」とありますが、Python 3.10 以降なら bisect_left(range(lo, hi), True, key=is_ok) のように、bisect でも判定関数のまま探せます。
  • std::lower_bound・std::upper_bound・std::partition_point(cpprefjp)
    • lower_bound は「指定した値以上の最初の位置」、upper_bound は「指定した値より大きい最初の位置」を返します。範囲がソートされていなくても、条件で区分化されていればよいこと、どちらも partition_point と同じ働きであることが書かれています。partition_point は判定関数を渡して境目を求める関数で、二分探索を一般化した形にあたります。
    • std::set や std::multiset に std::lower_bound を使うと、比較の回数は O(log⁡N)O(\log N) でもイテレータを進めるのに O(N)O(N) かかります。メンバ関数の s.lower_bound(x) を使ってください(cpprefjp の lower_bound のページにも、メンバ関数を使うようにと書いてあります)。

二分探索そのものを扱う講座はありませんが、二分探索を使う講座がいくつかあります。

  • Alien Trick
    • 「ちょうど kk 個選ぶ」という制約を、1 個ごとのペナルティ λ\lambda に置き換えて外し、λ\lambda を二分探索する手法の講座です。最適な個数が λ\lambda について単調になることを示し、二分探索の終了時に成り立つ条件まで丁寧に説明しています。難易度の高い講座です。
  • 永続セグメント木
    • 区間の kk 番目の値を求める問題で、ふつうに二分探索すると O(log⁡2N)O(\log^2 N) のところを、複数の木を同時に降りるセグメント木上の二分探索で O(log⁡N)O(\log N) にする方法を説明しています。
  • Wavelet Matrix(発展)
    • 「5. 総和に関する二分探索」の節で、単調な総和の条件を満たす境目を Wavelet Matrix の上で求めています。
  • 二分探索(日本語版 Wikipedia)、Binary search(英語版 Wikipedia)
    • 日本語版は英語版の訳です。重複がある場合に左端・右端を探す手続き(lower_bound・upper_bound にあたる)、順位や直前・直後の要素の求め方、指数探索などの変種が載っています。「実装上の問題」の節には、有名な本や Java の標準ライブラリで、真ん中の計算のオーバーフローのバグが長年見逃されていた話があります。答えで二分探索や実数の二分探索の話はありません。
    • 各言語のライブラリの節は、日本語版・英語版ともに古い情報を元にしています。
  • Binary search(cp-algorithms、英語)
    • 配列上の探索、lower_bound・upper_bound、単調な述語での探索とその正当性、答えで二分探索(平均値の最大化)、実数の探索(中間値の定理を使うので単調でなくてよい)、2 のべき乗の幅で進む方法、並列二分探索までを 1 ページで扱っています。オーバーフローの注意と C++20 の std::midpoint にも触れています。コードは C++ で、練習問題の一覧もあります。
    • 並列二分探索の節は、例の表と直後のコードで区間の取り方が違うので、読むときは混乱しないように気をつけてください。
  • Binary Search(USACO Guide、英語)
    • 単調な関数での二分探索の入門で、「true になる最後の位置」と「true になる最初の位置」の 2 つの書き方、よくある間違い(off-by-one、負の範囲、オーバーフロー)、練習問題の一覧があります。コードは C++・Java・Python から選べます。配列上の二分探索は、前提の別ページ Binary Search on a Sorted Array にあります。
    • 「Mistake 1」の Python のコードは hi = 0 になっていて(C++ と Java では hi = x)、説明している無限ループが起きません。「Mistake 2」の「負の奇数を 2 で割ると切り上がる」という説明は C++ と Java の話で、Python の // は切り捨てなので当てはまりません。
  • Binary Search(lovro、Topcoder、英語)
    • 述語が「no … no yes … yes」と並ぶときに二分探索できる、という形で一般化を説明した古典的なチュートリアルです。最後の no を探すときに真ん中を切り上げないと無限ループになる例や、実数の二分探索の打ち切り方(回数を固定する方法と、相対誤差で止める方法)もあります。
    • サイトの移行で表示が崩れていて、擬似コードのインデントが壊れていたり、例の数列が連結して表示されたりしています。練習問題のリンクは切れています。「Arrays.binary_search」は Java の Arrays.binarySearch の誤りです。
  • ABC146 C - Buy an Integer:値段は NN について単調増加なので、買える最大の NN を二分探索します。
  • 競技プログラミングの鉄則 A12 - Printer:tt 秒後までに印刷される枚数は tt について単調なので、KK 枚以上になる最小の tt を求めます。
  • 競プロ典型 90 問 001 - Yokan Party(★4):最小値の最大化です。上の解説を見てください。
  • ABC063 D - Widespread:爆発の回数を決め打ちして、すべての魔物を消せるかを判定します。
  • ABC023 D - 射撃王:得点を決め打ちすると風船ごとに割る期限が決まるので、期限の早い順に割れるかを判定します。
  • ABC174 E - Logs:最大値の最小化です。最も長い丸太を xx 以下にするのに必要な切断回数を数えます。
  • ABC144 E - Gluttony:成績を決め打ちし、組み合わせ方を貪欲に決めて、必要な修行の回数が KK 以下かを判定します。
  • ARC050 B - 花束:作る花束の個数を決め打ちして、作れるかを判定します。値が 101810^{18} まであるので、オーバーフローに注意が必要です。
  • ABC149 E - Handshake:幸福度の上がり方が xx 以上の握手が MM 通り以上あるような最大の xx を二分探索し、個数を数えるのにも二分探索を使います。
  • ABC034 D - 食塩水:平均値の最大化の典型です。上のけんちょんさんの記事が解説です。
  • ABC026 D - 高橋君ボール1号:f(t)f(t) は単調ではありませんが、f(0)<100f(0) < 100 で、tt が大きいと f(t)>100f(t) > 100 になるので、中間値の定理から f(t)=100f(t) = 100 となる tt を二分法で 1 つ見つけられます。
  • ABC269 E - Last Rook:行の範囲を半分に区切り、置かれているルークの数が行の数より少ないほうに空いた行がある、として 20 回以内の質問で探します。列も同じです。

Segment Tree Beats のリンク集

Segment Tree Beats について、参考になる記事や資料をまとめました。

Segment Tree Beats(Segment Tree Beats!、中国では「吉老师线段树」とも)は、2016 年ごろに吉如一(jiry_2)が中国の国家集訓隊論文で発表した、遅延評価セグメント木の拡張です。区間 chmin(ai←min⁡(ai,x)a_i \leftarrow \min(a_i, x))のように、遅延セグ木にそのままでは載らない作用を扱えます。名前はアニメ「Angel Beats!」に由来します。

考え方は「ノードへの作用が計算できないときは、子に再帰して計算し直す」というものです。区間 chmin と区間和の場合、各ノードに最大値・厳密に 2 番目に大きい値・最大値の個数・和を持ちます。xx が最大値以上なら何もせず、2 番目の値より大きければ最大値だけが xx に変わるので和もすぐ更新でき、それ以外のときだけ子に再帰します。再帰が起きる回数をポテンシャルで抑えるのがこの手法の要で、問題ごとに作用の設計と計算量の解析が必要です。

計算量は次のとおりです。

  • 区間 chmin・chmax と区間和だけなら、全体で償却 O((N+Q)log⁡N)O((N+Q) \log N) です。
  • 区間加算も混ぜると O((N+Q)log⁡2N)O((N+Q) \log^2 N) です。O((N+Q)log⁡N)O((N+Q) \log N) のままではないかという予想もありましたが、2025 年に Ω(Nlog⁡2N)\Omega(N \log^2 N) になる入力が見つかり、Θ(log⁡2)\Theta(\log^2) と分かりました。古い資料では「もしかしたら O(log⁡)O(\log) かも」と書かれていることがあります。
  • Segment Tree Beatsの実装メモ (基本まわり)(日々drdrする人のメモ)
    • 区間 chmin と区間最大値・区間和(HDU 5306 Gorgeous Sequence)、区間 chmin・chmax の場合を、図つきで実装の流れに沿って説明しています。ノードに何を持ち、どの条件で再帰を打ち切るかが分かります。最後に区間加算・区間代入を混ぜる場合にも少し触れています。計算量の解析は含みません。コードは C++ です。
    • コードの区間最大値は範囲外で 00 を返すので、負の値がある問題ではそのままでは使えません。
  • ABC256 Ex - I like Query Problem の解説(Nyaan、AtCoder 公式解説)
    • 区間を ⌊ai/x⌋\lfloor a_i / x \rfloor にする操作を含む問題で、解法 2 として Segment Tree Beats を説明しています。ACL の lazy_segtree の実装を土台に、作用が「失敗」したら子に再帰するように拡張する、という説明で、遅延セグ木を書ける人には一番入りやすい資料です。各ノードに「区間の値がすべて等しいか」のフラグを持ち、値が半分以下になることを使ったポテンシャルで O((N+Qlog⁡N)log⁡max⁡A)O((N + Q \log N) \log \max A) を示しています。
  • atcoder::lazy_segtree に1行書き足すだけの抽象化 Segment Tree Beats(ひとなので)
    • ACL の lazy_segtree の all_apply に if (d[k].fail) push(k), update(k); を書き足し、ノードに失敗フラグを持たせることで、汎用の Segment Tree Beats にする方法です。例題として yukicoder No.880(区間代入・区間 gcd)、CS Academy の And or Max(区間 and・or)、Library Checker の Range Chmin Chmax Add Range Sum のノードの設計があります。Beats の存在は知っているが実装したことはない人向けで、導入の解説はありません。
    • 注 4 の「composition 関数は lazy_segtree 内の二か所でしか呼ばれません」は、mapping 関数の誤りです。Library Checker の参考提出へのリンク(old.yosupo.jp)は切れています。
  • ABC430 G - Range Set Modifying Query の解説(kyopro_friends、AtCoder 公式解説)
    • 区間の集合に要素を追加・削除し、集合の大きさの最大値とその個数を答える問題を、上の記事の方法で解いています。区間 chmin とは違う種類の作用で、作用が失敗する条件と、失敗の回数の評価をどう考えるかの例になります。Beats を使わない別解も載っています。
  • A simple introduction to “Segment tree beats”(jiry_2、Codeforces、英語)
    • 考案者自身による紹介で、論文の 11 個の例題のうち 6 個(Task 1〜6)を扱っています。区間 chmin・chmax・加算に加え、各要素の過去の最大値などを扱う Historic Information の問題も含みます。再帰を打ち切る条件(break condition)と作用を載せる条件(tag condition)の枠組みと、ポテンシャルによる計算量の証明があります。
    • 冒頭で著者自身が、計算量の議論に穴があると書いています。加算を混ぜた Task 2 は O(nlog⁡2n)O(n \log^2 n) を示したうえで「たぶん O(nlog⁡n)O(n \log n) のまま」と書いていますが、下の記事により Θ(nlog⁡2n)\Theta(n \log^2 n) と分かりました。
  • Segment Tree Beats(ferin、HackMD)
    • 上の jiry_2 の記事を日本語に訳したメモで、6 つの Task と計算量の解析を日本語で読めます。
    • 実装が「ToDo」のままの節があるなど、未完成のメモです。Task 2 の「もしかしたら O(n log n) のままかも」は、今は否定されています。
  • Segment Tree Beatsの計算量解析(37zigen、Scrapbox)
    • 区間 chmin と区間和の場合に、償却 O(log⁡n)O(\log n) になることを図つきで証明しています。
    • 後半の区間加算を混ぜる場合は、証明の途中の一文に著者が後から「(これは嘘)」と付けていて、代わりの議論はありません。後半の証明は不完全なものとして読んでください。
  • The Time Complexity Lower Bound for Segment Tree Beats is log^2(Tony2_CF、Codeforces、英語)
    • 区間加算と全体への chmax だけで Ω(nlog⁡2n)\Omega(n \log^2 n) 回の再帰が起きる入力を作り、加算を混ぜたときの計算量が Θ(nlog⁡2n)\Theta(n \log^2 n) であることを示した 2025 年の記事です。これを受けて、Library Checker の Range Chmin Chmax Add Range Sum にもこの入力のテストケースが追加されました。
    • UOJ のブログに書かれた中国語の元記事を、Gemini 2.5 Pro で英語に機械翻訳したものです。
  • Segment Tree Beatsの実装メモ (応用的な例題まわり)(日々drdrする人のメモ)
    • 区間の要素を「最大値」と「それ以外」に分けて別々に情報を持つ考え方で、jiry_2 の Task 3(値が変わった回数の和)と Task 4(2 つの列の和の最大値)を実装しています。
  • Segment Tree Beatsの実装メモ (Historic Informationまわり)(日々drdrする人のメモ)
    • 各要素の過去の最大値・最小値・和(Historic Information)を扱う方法です。過去の最大値と今の値の差を持つことで、区間加算を chmax に言い換えます。
    • 図の説明の「xが最大値、yが二番目の最大値」と、_update_dmax の説明の「最大値・非最大値」は、どちらも「最小値」の誤りです(コードとそのコメントは正しいです)。

Segment Tree Beats を扱う講座はまだありません。セグメント木・遅延セグ木を扱う AAL Contest 001: Let’s use segtree! でも、Segment Tree Beats は範囲外と明記されています。

AtCoder Library(ACL)に Segment Tree Beats はありません。

日本語版・英語版の Wikipedia と cp-algorithms には、Segment Tree Beats の項目も節もありません。

  • Segment Tree Beats(USACO Guide、英語)
    • 区間 mod(Codeforces 438D)と、Range Chmin Chmax Add Range Sum を、chmin だけ → 加算を追加 → chmax も追加、と段階を追って説明しています。コードは C++ で、練習問題の一覧もあります。
    • 加算を混ぜたときの O((n+q)log⁡2n)O((n+q) \log^2 n) を「暫定的な上界」としていますが、今はこれで正しいと分かっています。
  • 区间最值操作 & 区间历史最值(OI Wiki、中国語)
    • 区間 chmin・chmax と Historic Information を、中国の OI の問題を例に説明しています。
  • 国家集训队2016论文集(PDF、中国語)
    • 吉如一の元の論文『区间最值操作与历史最值问题』が 99 ページから収録されています。

ローリングハッシュのリンク集

ローリングハッシュについて、参考になる記事や資料をまとめました。

ローリングハッシュは、文字列 S=s0s1…sn−1S = s_0 s_1 \dots s_{n-1} を基数 BB の多項式 s0Bn−1+s1Bn−2+⋯+sn−1s_0 B^{n-1} + s_1 B^{n-2} + \dots + s_{n-1} とみなし、素数 pp で割った余りをハッシュ値とする方法です。接頭辞のハッシュ hih_i と BiB^i を O(n)O(n) で前計算しておくと、部分文字列 S[l,r)S[l, r) のハッシュは hr−hlBr−lh_r - h_l B^{r-l} で O(1)O(1) で求まります(累積和と同じ考え方です)。ハッシュが違えば文字列は必ず違い、同じなら高い確率で同じなので、部分文字列どうしの一致判定が O(1)O(1) でできます。二分探索と組み合わせると、2 つの部分文字列の最長共通接頭辞(LCP)の長さが O(log⁡n)O(\log n) で求まり、辞書順の比較もできます。文字を 00 に対応させると、b と ab のように長さの違う文字列が同じハッシュになるので、文字は 11 以上の値に対応させます。

ハッシュは衝突する(違う文字列が同じハッシュになる)ことがあるので、mod と基数の選び方に注意が必要です。

  • mod と基数を固定すると、それに対して衝突する入力を作れます。Codeforces のように撃墜(Hack)のあるコンテストでは実際に狙われるので、基数は実行時に乱数で選びます。
  • mod を 2642^{64} にして符号なし 64 bit 整数のオーバーフローに任せる方法は、基数を乱数で選んでも、Thue–Morse 列から作った長さ 2102^{10}〜2122^{12} 程度の 2 つの文字列で衝突します。mod は素数にしてください。
  • mod 261−12^{61}-1 はメルセンヌ素数で、十分大きく、積の余りをビット演算で速く計算できるので、よく使われます。10910^9 程度の素数を使う場合は、mod を 2 つ以上組み合わせます。
  • mod が素数 pp で基数を一様ランダムに選ぶと、長さ nn の異なる 2 つの文字列が衝突する確率は (n−1)/p(n-1)/p 以下です(差を基数の n−1n-1 次以下の多項式とみると、その根は n−1n-1 個以下だからです)。比較の回数が多いと、確率はその回数倍まで増えます。
  • たくさんのハッシュ値を集めてその中に同じものがあるかを調べるときは、誕生日のパラドックスにより、ハッシュ値がおよそ p\sqrt{p} 個あると衝突しやすくなります。p≈109p \approx 10^9 の mod 1 つでは 10510^5 個程度でもほぼ確実に衝突します。

Python では整数の大きさに上限がないので、mod 261−12^{61}-1 の積もそのまま計算して % で余りを取れます。ただし、処理系によっては 64 bit を超える整数の計算がかなり遅くなるので、積を分割して 64 bit 以内に収める実装もあります。

  • ABC274 Ex - XOR Sum of Arrays の解説(Nyaan、AtCoder 公式解説)
    • 前半の「Rolling Hash とは?」の節が、ローリングハッシュの解説になっています。任意の部分列のハッシュを O(1)O(1) で求める方法と、基数を実行時にランダムに選べば、どんな入力でも衝突する確率が (N−1)/p(N-1)/p 以下になることの証明を説明しています。後半は、この問題のために XOR を加法とする体(Nimber)でローリングハッシュを作る話です。
    • 衝突耐性の説明の「A,BA, B であって H(A)≠H(B)H(A) \neq H(B) を満たすような」は、「A≠BA \neq B かつ H(A)=H(B)H(A) = H(B) を満たすような」の誤りです。
  • 安全で爆速なRollingHashの話(keymoon、Qiita)
    • 文字を 00 に対応させない、mod を大きくする、基数を実行時にランダムに選ぶ、2642^{64} などの 2 の累乗を mod にしない、という注意点をまとめたうえで、mod 261−12^{61}-1 の積を 64 bit 整数の範囲で計算する方法を図つきで説明しています。最後に __int128 を使う簡単な書き方にも触れています。コードは C# です。
    • 記事末尾の「実装のサンプル」へのリンクは、URL が壊れていて開けません。
  • 競プロ典型 90 問 047 の解説(E869120、画像)
    • 部分文字列の一致判定にローリングハッシュを使う解説の 2 枚目です。接頭辞のハッシュから部分文字列のハッシュを求める式を図で示し、mod を 2642^{64} にするとどんな基数でも WA になるケースが作れることにも触れています。
  • ハッシュを衝突させる話(hos)
    • mod が素数で基数を一様ランダムに選べば衝突する確率が (長さ −1-1)/mod 以下になる理由と、mod 2k2^k だと任意の奇数の基数で衝突する多項式が作れることを説明しています。後者から、長さ 4096 の 2 つの 01 文字列が mod 2642^{64} で衝突する例を作っています。
  • Rolling Hashを殺す話(EtoNagisa、スライド)
    • mod と基数を固定したローリングハッシュに対して、格子基底簡約(LLL)で衝突する文字列を作る方法と、mod と基数の組を 2 つにしても衝突させられる方法を紹介しています。結論は「mod を十分大きな素数にし、基数を実行時に乱数で選ぶ」です。最後に、mod 2642^{64} が基数によらず Thue–Morse 列で衝突する理由も説明しています。
  • Anti-hash test.(Zlobober、Codeforces、英語)
    • mod 2642^{64} のハッシュが、基数によらず Thue–Morse 列('A' + __builtin_popcount(i) % 2 で作る文字列)で衝突することを示した、この話の元になった記事です。
  • On the mathematics behind rolling hashes and anti-hash tests(dacin21、Codeforces、英語)
    • 基数をランダムにする方法と mod をランダムにする方法の衝突確率、乱数の種の取り方、ハッシュを複数使う場合や比較の回数が多い場合の見積もり、mod 261−12^{61}-1 の積の計算を説明しています。後半では、Thue–Morse 列、誕生日攻撃、木を使う攻撃、格子基底簡約など、衝突する入力の作り方を表にまとめて説明しています。固定の基数なら mod 261−12^{61}-1 でも衝突を作れることがわかります。
  • Hashing and Probability of Collision(rng_58、英語)
    • ローリングハッシュの衝突確率が Schwartz–Zippel の補題から N/MODN/\mathrm{MOD} 以下になることを説明し、同じ考え方で多重集合や根付き木の良いハッシュを作っています。グラフの同型判定を例に、理論的な保証のない「悪いハッシュ」についても書いています。
    • 根付き木の多項式の定義で、子の部分木を G1,…,GdG_1, \dots, G_d としているのは G1,…,GkG_1, \dots, G_k の誤記です。
  • AtCoder ABC 141 E - Who Says a Pun?(けんちょんの競プロ精進記録)
    • 下の練習問題の解説で、Suffix Array、Z algorithm、ローリングハッシュと二分探索による LCP、の 3 通りの解法を比べています。各組の LCP を二分探索で求める方法は遅く、長さを決め打ちして二分探索する方法にすると 1735 ms から 13 ms に速くなった、という話もあります。
    • ローリングハッシュのコードは mod 109+710^9+7・109+910^9+9 と基数を固定しています。
  • ABC331 F - Palindrome Query の解説(Nyaan、AtCoder 公式解説)
    • 左から計算したハッシュと右から計算したハッシュが一致するかで回文を判定し、連結したときのハッシュの式を使ってセグメント木に載せることで、1 文字の更新にも対応しています。mod 10910^9 程度で何組使えば失敗確率が十分小さくなるかの見積もりもあります。
  • ラビンカープ法のおはなし+二次元のロリハいいぞ(traP)
    • 後半の「二次元ローリングハッシュ」の節で、行列の (i,j)(i, j) 成分に Bn−i−1Cm−j−1B^{n-i-1} C^{m-j-1} を掛けて足す 2 次元のハッシュと、2 次元の累積和で部分行列のハッシュを求める方法を説明しています。前半は 1 次元の説明と、mod 109+710^9+7 1 つでは衝突して WA になった例です。
    • 基数と mod を固定していて、部分行列のハッシュを逆元を使って O(log⁡)O(\log) で求めています。冪を掛けて比べるようにすれば逆元はいりません。コードについては、筆者自身が「バグ消しきれてるか怪しい」と書いています。

ローリングハッシュを扱う講座はまだありませんが、衝突確率の根拠になる講座があります。

  • Fp\mathbb{F}_p 係数の多項式
    • 【定理 5】で Fp\mathbb{F}_p 係数の nn 次方程式の解が nn 個以下であることを示し、4 章で多変数に一般化した Schwartz–Zippel の補題を証明しています。基数をランダムに選んだローリングハッシュが衝突する確率の評価は、この定理からすぐ出ます。【問題 6】では、mod が素数でないと解の個数の評価が成り立たない例(mod 88 で x2−1x^2-1 の根が 4 個など)を扱っていて、mod 2642^{64} が危ない理由とつながります。
  • 文字列アルゴリズム(いかたこのたこつぼ)
    • 「Rabin-Karp法(ローリングハッシュ)」の節で、ハッシュの列で文字列を検索する考え方を図で説明しています。Python の実装例は mod 261−12^{61}-1 で、基数を乱数で 3 つ選び、Python の多倍長整数でそのまま計算しています。
  • RollingHashクラスをPythonでつくったよ。(hyouchun、Qiita)
    • 上の keymoon の記事の、積を分割して mod 261−12^{61}-1 を 64 bit 以内で計算する方法を、そのまま Python に移したクラスです。基数は乱数で選び、複数の文字列で同じ基数を共有します。説明はほとんどなく、コードと使い方だけです。
  • ローリングハッシュ (Rabin-Karp)(Competitive programming notebook)
    • 部分文字列のハッシュ、連結したハッシュ、二分探索による LCP の 3 つの機能を持つ Python のクラスと、mod を 2 つ使う例があります。
    • 「性質」の節の式 H(Cl,r)≡H(C1,r)−H(C1,l−1)H(C_{l,r}) \equiv H(C_{1,r}) - H(C_{1,l-1}) は、右辺の第 2 項に br−l+1b^{r-l+1} を掛けるのが正しいです。コードは正しく power[r-l] を掛けています。また、クラスの既定値は基数 34913491・mod 999999937999999937 の固定です。

AtCoder Library(ACL)にローリングハッシュはありません(文字列については z_algorithm や suffix_array があります)。

  • Rolling Hash (ローリングハッシュ)(Luzhiled’s Library)
    • mod 261−12^{61}-1 で基数を実行時に乱数で選ぶ C++ の実装です。部分文字列のハッシュ、LCP、ハッシュの連結のほか、先頭と末尾への文字の追加もできます。
  • Rolling Hash(Nyaan’s Library)
    • mod 261−12^{61}-1 で、基数を乱数で 2 つ(テンプレート引数で変更可)選ぶ C++ の実装です。部分文字列のハッシュ、文字列検索、LCP、部分文字列どうしの辞書順の比較があります。
  • ラビン-カープ文字列検索アルゴリズム(日本語版 Wikipedia)
    • ハッシュ値が一致したときだけ文字列そのものを比べる、という本来のラビン-カープ法を擬似コードで説明し、ローリングハッシュで次のハッシュ値を定数時間で求める例や、複数パターンの検索も扱っています。日本語版 Wikipedia には「ローリングハッシュ」の記事はありません。
    • 擬似コードのループが for i from 1 to n になっていますが、パターンの長さを mm とすると n−m+1n-m+1 までが正しいです。
  • Rabin–Karp algorithm(英語版 Wikipedia)
    • 内容は日本語版とほぼ同じで、擬似コードのループの範囲は正しく n-m+1 までです。ハッシュ関数をランダムに選ぶべきことにも触れています。競プロでよく使う「ハッシュが一致したら同じとみなす」使い方と違い、一致したら文字列を比べて確かめる方法です。
  • Rolling hash(英語版 Wikipedia)
    • 多項式によるローリングハッシュのほか、Rabin fingerprint、Buzhash、Gear hashing、rsync などで使う content-defined chunking まで扱っています。競プロとの関係は薄めです。
  • String Hashing(cp-algorithms)
    • 多項式ハッシュの定義、部分文字列のハッシュを逆元なしで比べる方法、異なる部分文字列の個数を O(n2)O(n^2) で数える例、ハッシュを 2 つ使って衝突確率を下げる話があります。mod 2642^{64} は基数によらず衝突する文字列が作れるので勧めない、とも書かれています。
    • コードは基数 3131・mod 109+910^9+9 の固定で、基数をランダムに選ぶ話はありません。異なる部分文字列の個数を数えるコードは、mod 109+910^9+9 1 つで多数のハッシュを unordered_set に入れるので、nn が大きいと誕生日のパラドックスにより衝突しやすいです。
  • String Hashing(USACO Guide)
    • Python のテンプレート、Schwartz–Zippel の補題による衝突確率、誕生日のパラドックスの警告、例題の解説と問題の一覧があります。後半は集合を XOR で表す Zobrist hashing です。
    • テンプレートは基数 99739973・mod 109+910^9+9 の固定です。本文の警告にある通り、多数の文字列を扱うときは mod 261−12^{61}-1 にし、撃墜のあるコンテストでは基数を乱数で選んでください。
  • AOJ ALDS1_14_B - 文字列検索:文字列 TT の中で文字列 PP が現れる位置をすべて出力します。ローリングハッシュの基本の確認に使えます。
  • ABC141 E - Who Says a Pun?:重ならずに 2 回以上現れる部分文字列の最長の長さを、長さを二分探索してハッシュの重複で判定します。公式解説の本筋は Z algorithm で、ローリングハッシュは別解です。
  • 競プロ典型 90 問 047 - Monochromatic Diagonal(★7):TT の文字をうまく置き換えると、斜めの列が一色かどうかは、SS と TT の接頭辞と接尾辞の一致判定になります。
  • ABC150 F - Xor Shift:隣どうしの XOR の列に直すと、巡回シフトした列との一致判定になります。公式解説は KMP 法で、典型 90 問 047 の解説で類題として挙げられています。
  • ABC135 F - Strings of Eternity:ss をつなげた文字列の各位置で tt と一致するかを求めて、グラフの最長パスを考えます。公式解説に、mod 2642^{64} で衝突する入力を用意してあると書かれています。
  • ABC284 F - ABCBAC:TT の前半と、後半を反転した文字列の一致判定を、各 ii について O(1)O(1) で行います。公式解説は Z algorithm ですが、ローリングハッシュでも解けると書かれています。
  • ABC331 F - Palindrome Query:1 文字の更新と回文判定のクエリを、両向きのハッシュを載せたセグメント木で処理します。
  • ABC312 Ex - snukesnuke:文字列を何回か繰り返した文字列がすでに使われているかを判定します。公式解説の本筋は Z algorithm で周期を求める方法ですが、ローリングハッシュを使う解法も載っています。
  • AOJ ALDS1_14_C - パターン検索:H×WH \times W の文字の盤面から R×CR \times C のパターンを探します。2 次元のローリングハッシュの練習になります。
  • ABC274 Ex - XOR Sum of Arrays:2 つの区間の XOR をとった列と別の区間の辞書順の比較を、XOR と相性のよい体の上のローリングハッシュと LCP の二分探索で行います。

Suffix Automaton のリンク集

Suffix Automaton について、参考になる記事や資料をまとめました。

Suffix Automaton は、文字列 SS のすべての部分文字列を受理する最小の DFA(決定性有限オートマトン)です(終端状態を SS の suffix に限ると、suffix だけを受理する最小の DFA になります)。各状態は、SS の中での出現位置の終端の集合(endpos)が等しい部分文字列の集まりを表します。∣S∣=N≥2|S| = N \ge 2 のとき状態数は 2N−12N - 1 以下、N≥3N \ge 3 のとき遷移数は 3N−43N - 4 以下で、1 文字ずつ末尾に追加するオンラインのアルゴリズムで線形時間で構築できます。各状態から「その状態に入らない最長の suffix」の状態へ張る suffix link は木になり、この木は逆文字列 rev(S)\mathrm{rev}(S) の suffix tree と同じ形です。

遷移を長さ σ\sigma(文字の種類数)の配列で持つと速いですが、メモリは O(Nσ)O(N\sigma) です。英小文字で N=5×105N = 5 \times 10^5 なら、状態が最大 10610^6 個なので、int の配列で 100 MB ほどになります。map などで持つとメモリは O(N)O(N) ですが、構築が O(Nlog⁡σ)O(N \log \sigma) になり、定数倍も重くなります。定番の使い方には、異なる部分文字列の個数(len(link(v))\mathrm{len}(\mathrm{link}(v)) を suffix link の先の状態の最長の長さとして、初期状態以外の各状態 vv について len(v)−len(link(v))\mathrm{len}(v) - \mathrm{len}(\mathrm{link}(v)) を足す。答えは 64 bit 整数が必要)、ある文字列の出現回数(suffix link の木の部分木で endpos の大きさを数える)、2 つの文字列の最長共通部分文字列(片方の Suffix Automaton の上でもう片方を読み、遷移できないときは suffix link をたどる)などがあります。

  • Suffix Automaton(よすぽの日記)
    • Suffix Automaton を rev(S)\mathrm{rev}(S) の圧縮した Suffix Tree から作れることを図で示し、頂点数・辺数の上限の証明、構築アルゴリズム(clone の判定に len\mathrm{len} を使う)、構築の計算量、異なる部分文字列の個数などの応用を短く説明しています。最後に C++ の実装があります。下の ABC433 G の公式解説でも紹介されています。
    • 「性質」と「問題例」の節で「部分列」と書いているところは「部分文字列」の意味です。また、実装は last を戻して複数の文字列を追加する使い方には対応していません(下の「複数の文字列」の節を参照)。
  • Suffix Automaton(cp-algorithms、英語)
    • endpos と suffix link の定義から、構築アルゴリズム、その正当性と計算量、状態数 2n−12n - 1・遷移数 3n−43n - 4 の証明までを順に説明しています。後半の応用の節は、異なる部分文字列の個数、辞書順 kk 番目の部分文字列、出現回数、最初の出現位置、2 つや複数の文字列の最長共通部分文字列など 11 個あります。e-maxx.ru のロシア語の記事の翻訳です。
    • コードは C++ で、遷移を map<char, int> で持ち、状態をグローバルな配列に入れる書き方です。遷移を配列で持つ場合のメモリと速度の違いにも触れています。

構築は、末尾に文字 cc を追加するたびに、直前の文字列全体の状態から suffix link をたどって cc の遷移を張り、必要なら状態を分割(clone)する、という手順です。

  • Suffix Automatonでもやもやした部分をなんか書いただけ(迷いませんか?)
    • cp-algorithms の構築の手順について、「なぜ suffix link をさかのぼりながら遷移を張ってよいのか」「なぜ clone が必要なのか」などの疑問に答える形で補足しています。S=abcbccS = \texttt{abcbcc} に 1 文字ずつ追加していく図があります。
    • 筆者自身が「多分」と書いている箇所もあり、cp-algorithms と合わせて読む補足として使うのがよいです。
  • A short guide to suffix automata(quasisphere、Codeforces、英語)
    • 「部分文字列を 1 文字ずつ聞かされて、出現しうる位置の集合だけを覚えておく」というゲームから状態の意味を導き、suffix link、構築、C++ の実装、簡単な応用を短く説明しています。suffix link の木が逆文字列の suffix tree になることにも触れています。
    • 「異なる部分文字列の個数は経路の個数」とあるのは、空の経路を含むので、実際の個数は 11 を引いたものです。

複数の文字列のすべての部分文字列を受理するオートマトン(一般化 Suffix Automaton)は、1 つの Suffix Automaton に「last を初期状態に戻してから次の文字列を追加する」ことを繰り返して作ることもあります。ただし、そのままだと追加したい文字の遷移がすでにある場合に無駄な状態ができるので、その場合を別に扱う必要があります。

  • 广义后缀自动机(OI Wiki、中国語)
    • 複数の文字列から Trie を作り、BFS の順に Suffix Automaton の構築を行う方法を説明しています。区切り文字で連結する方法や last を戻す方法(「伪广义后缀自动机」)の問題点、すべての文字列の異なる部分文字列の個数や複数の文字列の最長共通部分文字列への応用も扱っています。C++ のコードは遷移を配列で持っています。
  • 下の USACO Guide の例題「Standing Out from the Herd」の解答コードは、last を戻して追加する方法で、すでに遷移がある場合も正しく扱っています。

suffix link の木は rev(S)\mathrm{rev}(S) の suffix tree なので、rev(S)\mathrm{rev}(S) の Suffix Automaton を作れば SS の suffix tree が得られ、さらにその DFS 順から SS の Suffix Array が得られます。Suffix Array と LCP 配列で解ける問題の多くは Suffix Automaton でも解けるので、どちらで解くかは好みや問題によります。

  • String Suffix Structures(USACO Guide、英語)
    • Suffix Automaton、Suffix Tree、Suffix Array を相互に変換する方法(suffix tree の DFS から Suffix Array を作る、Suffix Array と LCP 配列から suffix tree を作る、Suffix Automaton の suffix link から suffix tree を作る)を C++ のコード断片で紹介し、例題を一般化 Suffix Automaton で解いています。どの構造でも解ける問題の一覧があります。解説は短く、詳しくは cp-algorithms などへのリンクに任せています。
    • suffix tree を扱う 2 つのコード断片は、ループ変数がグローバルな配列と同じ名前(c や l)になっていて、そのままではコンパイルできません。

Suffix Automaton を扱う講座はまだありません。文字列の分類にある講座は、今のところ「文字列の並べ替えと辞書順最小化」だけです。

  • string/suffix_automaton.hpp(maspy’s library)
    • C++ の実装で、遷移を長さ sigma(既定は 26)の配列で持ちます。構築後に状態を len\mathrm{len} の昇順(トポロジカル順)に並べ替え、各状態の出現回数と出現位置の最小・最大も求めます。suffix link の木を作る関数、SS の区間 [L,R)[L, R) に対応する状態を求める関数、もう 1 つの文字列を読みながら最長一致を追う next もあります。ドキュメントはなく、説明はコード中のコメントだけです。

百科事典・英語・中国語の資料

Section titled “百科事典・英語・中国語の資料”
  • Suffix automaton(英語版 Wikipedia)
    • 歴史、right context(右側の文脈)と endpos による状態の定義、suffix tree との関係、状態数と遷移数の上限(それぞれ abn−1ab^{n-1} と abn−2cab^{n-2}c で達成されること)、擬似コードつきの構築、CDAWG・複数の文字列・スライディングウィンドウへの一般化、応用までを網羅しています。
    • 日本語版の「接尾辞オートマトン」は数行の短い記事で、図も suffix だけを受理する非決定性のオートマトンなので、競プロの Suffix Automaton を知るには向きません。
  • 后缀自动机 (SAM)(OI Wiki、中国語)
    • cp-algorithms と同じ e-maxx.ru の記事の翻訳がもとで、内容もほぼ同じです(構築、正当性、状態数と遷移数、11 個の応用)。図が多く、最後に練習問題の一覧があります。
  • Library Checker - Number of Substrings:異なる部分文字列の個数を求めます。N≤5×105N \le 5 \times 10^5 で、ライブラリの verify 用です。
  • CSES - Distinct Substrings:上と同じく異なる部分文字列の個数を求めます。n≤105n \le 10^5 です。
  • CSES - Substring Distribution:長さごとに異なる部分文字列の個数を求めます。各状態が受け持つ長さの区間に、いもす法で 11 を足します。
  • CSES - Counting Patterns:各パターンの出現回数を求めます。suffix link の木で各状態の endpos の大きさを数えておきます。
  • SPOJ - LCS(Longest Common Substring):長さ 250000250000 以下の 2 つの文字列の最長共通部分文字列の長さを求めます。
  • SPOJ - SUBLEX(Lexicographical Substring Search):異なる部分文字列のうち辞書順で KK 番目のものを答えるクエリに答えます。各状態から出る経路の個数を数えておきます。
  • ABC433 G - Substring Game:Suffix Automaton の上でコマを動かすゲームに言い換え、後退解析で勝敗を求めます(公式解説)。
  • Codeforces 235C - Cyclical Quest:xix_i の巡回シフトのどれかと一致する ss の部分文字列の個数を求めます。xixix_i x_i を ss の Suffix Automaton の上で読み、同じ状態を重複して数えないようにします。
  • 競プロキャンプ2026関西 J - Substring Query
    • SS の Suffix Automaton の上で各クエリの文字列 TT を前から読み、遷移できないときは suffix link をたどって、SS と TT の最長共通部分文字列の長さを求めています。

MEX のリンク集

MEX について、参考になる記事や資料をまとめました。

MEX(minimum excluded value)は、非負整数の集合に含まれない最小の非負整数です。たとえば mex{0,1,2,4}=3\mathrm{mex}\{0, 1, 2, 4\} = 3、mex{1,2}=0\mathrm{mex}\{1, 2\} = 0、mex ∅=0\mathrm{mex}\,\emptyset = 0 です。長さ NN の列の MEX は NN 以下なので、NN より大きい値は無視してよく、長さ N+1N + 1 の配列で「どの値が含まれるか」を数えれば O(N)O(N) で求まります。問題によっては「含まれない最小の正の整数」を MEX と呼ぶこともあるので、0 始まりか 1 始まりかを問題文で確かめてください。

MEX はゲームの問題にもよく出てきます。不偏ゲームの各局面の Grundy 数は「1 手で移れる局面の Grundy 数の MEX」で定義され、Sprague-Grundy の定理により、いくつかのゲームを並べたゲームの Grundy 数は各ゲームの Grundy 数の XOR になります。

値の追加・削除をしながら MEX を求めたいときは、各値の個数を数えておき、00 から NN までの「含まれない値」を set に入れて最小値を取る方法や、値を添字にしたセグメント木の上で二分探索する方法があります。区間 [l,r)[l, r) の MEX を答えるクエリは、右端の順に処理して各値の最後の出現位置をセグメント木で持つ方法(オフライン)や、永続セグメント木(オンライン)で解けます。セグメント木そのものについては セグメント木のリンク集 も見てください。

  • Mexを計算する(magurofly、Scrapbox)
    • 追加・削除をしながら MEX を求める方法として、区間 min のセグメント木を使う方法(含まれる値の位置を ∞\infty、含まれない値の位置を自分自身の値にして全体の min を取る)と、下で紹介する「区間を set で管理するテク」の 2 つを短くまとめています。多重集合にするときは値ごとに個数を持つことにも触れています。コードはありません。
  • mex のライブラリ化(saka_pon、Qiita)
    • 要素数が MM 以下なら MEX も MM 以下なので、[0,M)[0, M) のうち含まれない値だけを順序つき集合で持てばよい、という考え方から、追加・削除と MEX の取得を O(log⁡M)O(\log M) で行うクラスを作っています。多重集合版と、順序つき集合の代わりに削除可能な優先度付きキューを使う版もあります。コードは C# です。
  • 要素の追加・削除と mex を対数時間で処理するよ(えびちゃんの日記)
    • 集合に含まれる連続した整数を 1 つの区間として set<pair> で持ち、「xx 以上で集合に含まれない最小の整数」を求める方法です。値の上限に依存せず、区間の追加にも対応できます。手順は文章で説明していて、C++ と Rust のコードは AtCoder の提出へのリンクです。
  • 「区間をsetで管理するやつ」をPythonでライブラリ化しました(hibit、Qiita)
    • 上の記事の方法を、半開区間で管理する Python のクラスにしています。sortedcontainers を使います。
    • 記事の最後にある区間の追加・削除のコードは、著者が「ChatGPT に書かせた、verify が済み次第反映させる」と書いているもので、検証されていません。
  • 石取りゲーム(Nim)(いかたこのたこつぼ)
    • Nim の必勝法とその証明、最後に取った方が負けの逆形ルール、一度に KK 個の山から取れる NimK を説明したあと、Grundy 数による一般化と、取れる石の数に上限・下限がある場合などの例を Grundy 数の表で追っています。
    • 石の個数の XOR が 00 の状態を「必勝形」(渡した側が勝つ形)と呼んでいます。受け取った側から見ると負けの状態なので、読むときに注意してください。
  • tech005:NimとGrundy数(takeo1116)
    • Nim の必勝法と Grundy 数の定義、Grundy 数の XOR についての性質を 1 ページで短くまとめています。証明やコードはありません。
  • 競技プログラミングにおけるゲーム問題まとめ(はまやんはまやんはまやん)
    • Nim、Grundy 数、後退解析、真似をする戦略、ミニマックス法などの手法ごとに、問題の一覧を集めたページです。説明は箇条書きで短いです。
    • Grundy 数の定義が「遷移可能な状態の Grundy 数の中で最小の非負整数」となっていますが、正しくは「遷移先の Grundy 数に含まれない最小の非負整数」です。
  • Offline Range MEX queries in O(log n)(one_autum_leaf、Codeforces、英語)
    • クエリを右端の順に処理し、各値の最後の出現位置を区間 min のセグメント木で持ちます。「最後の出現位置が ll より前」である最小の値をセグメント木の上で降りて探すと、それが区間 [l,r][l, r] の MEX です。C++ のコードがあります。
    • 例の数列 [6,1,0][6, 1, 0] は、冒頭の制約 ai≤na_i \le n を満たしていません。nn より大きい値は MEX に関係しないので、答えは変わりません。
  • Collection of little techniques(-is-this-fft-、Codeforces、英語)
    • 小さなテクニック集の「2. Avoiding logs in Mo’s algorithm」の節で、区間 MEX のクエリを Mo’s algorithm で解く例を扱っています。区間の端を動かすたびに set を更新すると O(NNlog⁡N)O(N\sqrt{N}\log N) になるので、値を N\sqrt{N} 個ずつのブロックに分けて、追加・削除を O(1)O(1)、MEX の取得を O(N)O(\sqrt{N}) にする方法を説明しています。

MEX や Grundy 数を扱う講座はまだありませんが、関連する講座があります。

  • 競技プログラミング基本用語集
    • 「4.10. mex」の節に、MEX の定義と例があります。多重集合や列にも同じ記号を使うこと、問題によっては正の整数で定義していることにも触れています。
  • 永続セグメント木
    • 過去のすべてのバージョンにアクセスできるセグメント木の講座です。MEX には触れていませんが、区間 MEX のクエリにオンラインで答えるときは、下の kopricky さんの実装のように、各接頭辞のバージョンを持つ永続セグメント木を使います。
  • StaticRangeMexQuery(kopricky アルゴリズムライブラリ)
    • 更新のない列で、区間 [l,r)[l, r) の MEX にオンラインで O(log⁡n)O(\log n) で答える C++ の実装です。
    • 説明文ではフラクショナルカスケーディングを使うと書かれていますが、載っているコードは永続セグメント木を使っています。また、ページには「verify していません」と書かれています。
  • intervals_set.cpp(drken1215/algorithm、GitHub)
    • 区間を set で管理する C++ の構造体で、get_mex(p) が pp 以上で含まれない最小の値を返します。区間に値を持たせて更新することもできます。ABC330 E などで verify されています。ドキュメントはなく、コード中のコメントだけです。
  • Mex (mathematics)(英語版 Wikipedia)
    • 整列集合の部分集合の MEX として定義し、順序数を含む例、Sprague-Grundy の定理での使われ方、グラフの貪欲彩色での使われ方を説明しています。1 つの山の Nim や、一度に 3 個まで取れる Nim の Grundy 数の計算例があります。日本語版の記事はありません。
  • Sprague–Grundy theorem(英語版 Wikipedia)
    • 不偏ゲームの局面を集合として再帰的に表し、ゲームの和、局面の同値、定理の証明までを扱っています。抽象的な書き方で、記事の冒頭にも「技術的すぎる」という注意書きがあります。
    • 日本語版は定理の内容を述べた数行だけの記事です。
  • MEX (minimal excluded) of a sequence(cp-algorithms)
    • set を使う O(Nlog⁡N)O(N \log N) の方法と、真偽値の配列を使う O(N)O(N) の方法、要素を更新しながら MEX を求める方法(セグメント木で二分探索する方法の説明と、map と「含まれない値の set」を使う C++ のクラス)を扱っています。長さ NN の列の MEX が NN 以下であることにも触れています。最後に練習問題の一覧があります。
  • Sprague-Grundy theorem. Nim(cp-algorithms)
    • Nim の必勝法の証明、逆形ルール、石を増やせる Nim の補題を使った Sprague-Grundy の定理の証明、ゲームが和に分かれるときの Grundy 数の計算、周期を探すことの有用性を説明しています。例として、1 列のマスに隣り合わないように × を置くゲームを扱っています。
  • ABC245 B - Mex:数列の MEX を求める基本問題です。
  • HHKB2020 C - Neq Min:先頭から 1 つずつ値を追加しながら、毎回 MEX を出力します。MEX は減らないので、前回の答えから増やしていけば全体で線形時間です。
  • ABC290 C - Max MEX:KK 個の要素を選んだときの MEX の最大値を求めます。MEX が KK を超えないことに気づくのがポイントです。
  • ABC330 E - Mex and Update:1 点更新のたびに数列全体の MEX を出力します。NN より大きい値は無視して、含まれない値を set などで管理します。
  • ABC272 E - Add and Mex:毎回 AiA_i に ii を足したあとの MEX を求めます。各 AiA_i が [0,N][0, N] にいる回数は全体で調和級数の O(Nlog⁡N)O(N \log N) 回なので、その回だけを記録します。
  • ABC194 E - Mex Min:長さ MM のすべての区間の MEX の最小値を求めます。区間を 1 つずつずらしながら、各値の個数を更新します。
  • ABC368 F - Dividing Game:整数を自身以外の約数に置き換えるゲームで、各整数の Grundy 数を求めて XOR を取ります。
  • ABC297 G - Constrained Nim 2:1 回に LL 個以上 RR 個以下を取る Nim です。小さい場合の Grundy 数を計算して規則性を見つけます。
  • 競プロ典型 90 問 031 - VS AtCoder(★6):白石と青石の個数の組ごとに Grundy 数を DP で求め、山ごとの XOR で勝敗を判定します。
  • ABC206 F - Interval Game 2:区間を選ぶと左右の 2 つのゲームに分かれるので、範囲ごとの Grundy 数を区間 DP で求めます。
  • Blitz Round #25 A - Sum vs MEX
    • MEX を「含まれない最小の正の整数」とする問題で、全体の MEX が必ず n+1n + 1 になることから nn が奇数なら不可能とし、偶数なら 11 を最後に置いて途中の MEX をすべて 11 にする順列を構成しています。

最大部分配列問題のリンク集

最大部分配列問題について、参考になる記事や資料をまとめました。

最大部分配列問題は、数列の連続する部分列(部分配列)のうち、和が最大のものを求める問題です。全部の区間を調べると O(N2)O(N^2) ですが、Kadane のアルゴリズムを使うと O(N)O(N) で解けます。左から順に「その位置で終わる部分列の和の最大値」cc を c←max⁡(c+Ai,Ai)c \gets \max(c + A_i, A_i) で更新していき、cc が取った値の最大値が答えです。累積和 SS で見ると、右端 rr を決めたときの最大値は「SrS_r − それまでの SS の最小値」なので、累積和と累積 min でも O(N)O(N) で求まります。Kadane のアルゴリズムで持っている値は、この差にあたります。最小の和を求めたいときは、符号を反転させれば同じです。

空の部分列(和は 00)を許すかどうかで答えが変わるので、問題文をよく確認してください。許すなら答えは 00 以上で、許さないなら全要素が負のときの答えは最大の要素です。紹介する記事やコードでも扱いが分かれていて、初期値を 00 にするか A1A_1 にするかで違いが出ます。また、和は 64 bit 整数で持つ必要があることが多いです。

区間の最大部分配列和を、要素の更新をはさみながら何度も求めたいときは、セグメント木を使います。各ノードに「区間全体の和」「接頭辞の和の最大値」「接尾辞の和の最大値」「部分配列の和の最大値」の 4 つを持たせると、1 点の更新と区間のクエリがどちらも O(log⁡N)O(\log N) でできます。累積和そのものについては 累積和・いもす法のリンク集 も見てください。

  • Kadane’s Algorithm | 最大部分配列 問題(Ark’s Blog)
    • O(n3)O(n^3) と O(n2)O(n^2) の全探索、分割統治による O(nlog⁡n)O(n \log n)、Kadane のアルゴリズムによる O(n)O(n) を順に紹介しています。Kadane のアルゴリズムは、全探索の式の max⁡\max の順番を入れ替えて、右端 jj で終わる部分列の和の最大値 sjs_j の漸化式を導く形で説明しています。D 言語のコードつきで、空の部分列は許さない設定です。分割統治の節は概要だけです。
  • Kadane’s Algorithm - Maximum subarray problem(Janos、Zenn)
    • 全探索と Kadane のアルゴリズムを Python で比べています。先頭からの和が初めて負になる位置 kk より前から始まる部分列は考えなくてよい、という形で O(N)O(N) になる理由を説明しています(本人も厳密な証明ではないと書いています)。空の部分列は許さず、全要素が負なら最大の要素を返す実装です。
    • コードの List と inf は import されていないので、そのままでは動きません。
  • [競プロ][Max Subarray] Kadane’s Algorithm解説(awesam、Qiita)
    • DP[i]\mathrm{DP}[i] を「AiA_i で終わる部分配列の和の最大値」とする DP として説明し、答えは DP[n−1]\mathrm{DP}[n-1] ではなく DP\mathrm{DP} 全体の最大値であることを強調しています。LeetCode の Maximum Subarray を解く C++ のコードつきです。
    • コードは和を int で持っています。
  • Search the subarray with the maximum/minimum sum(cp-algorithms、英語)
    • 「Algorithm 1」で累積和から「それまでの最小の累積和」を引く方法を、「Algorithm 2」で Kadane のアルゴリズムを、それぞれ区間の位置も求めるコードつきで説明しています。後半では、長さに制約がある場合、2 次元版(下の節)、平均の最大値を二分探索で求める方法にも触れています。
    • コードは和を int で持っています。答えの初期値を a[0] にしているので空の部分列は許さない設定ですが、本文ではそのことに触れていません。また、Kadane のアルゴリズムを「1984 年に提案」としていますが、英語版 Wikipedia の歴史の節によると、考案されたのは 1977 年に問題が提案されてまもなくです。
  • More on Prefix Sums(USACO Guide、英語)
    • 最初の「Max Subarray Sum」の節で、固定した右端 rr について p[r]−min⁡l<rp[l]p[r] - \min_{l < r} p[l] を取る方法を説明し、C++・Java・Python のコードを載せています。下の CSES - Maximum Subarray Sum が例題です。別解として Kadane のアルゴリズムのコードも折りたたんで載っています。
    • 別解の Python のコードは数値を 1 行に 1 つずつ読んでいますが、CSES の入力は 1 行に並んでいるので、そのままでは動きません。
  • Maximum Subarray Sum using Divide and Conquer algorithm(GeeksforGeeks、英語)
    • 列を半分に分け、「左半分の答え」「右半分の答え」「中央をまたぐ部分列の最大値」の 3 つの最大値を取る O(nlog⁡n)O(n \log n) の方法を、C++・Java・Python などのコードで示しています。中央をまたぐ部分は、中央から左に伸ばした和の最大値と右に伸ばした和の最大値の和です。最後に Kadane のアルゴリズムのほうが良いと書いています。
    • コードは和を int で持っています。また、空間計算量を O(n)O(n) としていますが、追加で使うのは再帰の深さぶんの O(log⁡n)O(\log n) です。

左右の答えと「またぐ部分」を組み合わせるこの考え方を、区間ごとに前計算して持っておくのが次のセグメント木による方法です。

  • 最大部分配列問題(連続部分列の総和の最大値)をセグ木に載せる(hotman’s blog)
    • 「左端を含む最大値」「右端を含む最大値」「区間の最大値」「区間の総和」の 4 つ組がモノイドになり、2 つをつなげるときの式を分割統治と同じ考え方で導いています。短い記事で、単位元やコードは載っていません。
  • Finding subsegments with the maximal sum(cp-algorithms、英語)
    • セグメント木の記事の一節で、同じ 4 つの値を持たせる方法を、combine 関数と再帰のセグメント木の C++ のコードで説明しています。こちらは空の部分列を許す設定で、葉では和以外の値を max⁡(0,x)\max(0, x) にしています。
    • コードは値を int で持っています。

下の AtCoder Algorithm Lectures の講座は、空の部分列を許さない設定で同じモノイドを説明しています。設定によって単位元や葉の値が変わるので、見比べると違いがわかります。

長方形の領域の和の最大値を求める 2 次元版は、使う行の範囲(上端と下端)を全通り試し、各列の和を並べた 1 次元の列で最大部分配列問題を解くと、N×MN \times M のグリッドで O(N2M)O(N^2 M) です。

  • Two-dimensional case of the problem(cp-algorithms、英語)
    • 上の方法で O(n3)O(n^3) になることを説明しています。より速いアルゴリズムも知られているものの、複雑で実用的ではないことや、全点対最短路(min-plus の行列積)との関係にも触れています。
  • 区間クエリのためのモノイド設計
    • 「5.4 最大部分配列和」の節で、1 点更新と区間の最大部分配列和のクエリに答えるために、区間全体の和・接頭辞の和の最大値・接尾辞の和の最大値・答えの 4 つを持たせる設計を、結合の式と C++ のコードで説明しています。空でない部分列を対象にしていて、単位元は (−∞,−∞,−∞,0)(-\infty, -\infty, -\infty, 0) です。空の部分列を許す文献もあり、その場合は単位元が変わることにも触れています。
    • 「7.6 最大部分配列和(再考)」では、同じ問題を max-plus 半環上の 3×33 \times 3 行列の積として扱い、積の形が決まっているので 4 つの成分だけ持てばよいことを説明しています。「10.2」の関連問題には、下の CSES - Subarray Sum Queries が空の部分列の扱いの違いの注意つきで載っています。
    • −∞-\infty の具体的な値は書かれていません。−∞-\infty どうしを足すことがあるので、long long の最小値を使うとオーバーフローします。−1018-10^{18} 程度にしておくのが安全です。

主要な競プロライブラリ(ACL、Nyaan’s Library、Luzhiled’s Library など)には、最大部分配列問題そのものの実装はありません。セグメント木に載せるときは、上の講座の S、op、e をセグメント木のライブラリに渡します。

  • segtree のドキュメント(AtCoder Library)
    • ACL のセグメント木に渡す型 S・演算 op・単位元 e の決め方が書かれています。セグメント木のライブラリ全般は セグメント木のリンク集 を見てください。
  • Maximum Subarray Sum - Kadane’s Algorithm(GeeksforGeeks、英語)
    • O(n2)O(n^2) の全探索と Kadane のアルゴリズムを、C++・C・Java・Python・C#・JavaScript のコードで示しています。空でない部分列を対象にしていて、初期値を arr[0] にしています。
    • コードは和を int で持っています。C のコードは int を返す関数の結果を %lld で出力していて、書式が合っていません。

最大部分配列問題の記事は日本語版 Wikipedia にはありません。

  • Maximum subarray problem(英語版 Wikipedia)
    • 問題の定義と性質、歴史(Grenander が 2 次元版の簡略化として 1977 年に提案し、Shamos の O(nlog⁡n)O(n \log n) の分割統治を経て Kadane が O(n)O(n) の方法を考案したこと)、応用、Kadane のアルゴリズムを扱っています。Kadane のアルゴリズムは、空の部分列を許さない版と許す版の両方を Python のコードで示し、ループ不変条件で正しさを説明しています。2 次元版が O(n3)O(n^3) で解けることや、和の大きい順に kk 個の部分配列を求める一般化にも触れています。
    • 「Computing the best subarray’s position」の節は、区間の位置も求められると書いているだけで、コードはありません。
  • Donuts プロコンチャレンジ2014 C - ソーシャルゲーム:空でない連続部分列の和の最大値を求める基本形です。全要素が負のときは答えも負になります。
  • AtCoder Weekday Contest 0074 Beta B - 連続区間の最大和:空の区間を許す基本形で、答えは 00 以上です。和は 32 bit 整数に収まりません。
  • CSES - Maximum Subarray Sum:空でない部分配列の和の最大値を求めます。値が 10910^9 までなので、64 bit 整数が必要です。
  • CSES - Maximum Subarray Sum II:長さが aa 以上 bb 以下の部分配列に限ります。累積和の最小値を取る範囲が窓になるので、スライド最小値などで解けます。
  • ARC174 A - A Multiply:区間を CC 倍したときの総和の増分は (C−1)Ai(C - 1)A_i の区間和なので、この列の空を許す最大部分配列和を元の総和に足します。CC は負や 00 のこともあります。
  • ARC137 B - Count 1’s:00 を +1+1、11 を −1-1 に置き換えると、1 の個数の増分は区間和になり、取りうる値は空を許す最小部分配列和から最大部分配列和までの整数すべてです。
  • ABC466 E - Range Flip:操作する区間は交わらないとしてよく、Bi−AiB_i - A_i の列から高々 KK 個の交わらない区間を選んで和を最大化する問題になります。
  • AtCoder Weekday Contest 0097 Beta D - 最大長方形部分和:2 次元版です。空の領域は選べず、N,M≤500N, M \le 500 なので O(N2M)O(N^2 M) の方法が間に合います。
  • CSES - Subarray Sum Queries:1 点の更新のたびに、配列全体の最大部分配列和を答えます。空の部分配列を許します。
  • CSES - Subarray Sum Queries II:更新はなく、区間 [a,b][a, b] の中の最大部分配列和を答えるクエリを処理します。空の部分配列を許します。
  • Blitz Round #25 B - Jump Trip Score
    • 高々 1 回の跳躍で飛ばす区間を、接頭辞と接尾辞の和の最大値を累積和で求めて境目を全通り試す方法で解き、空を許す最小部分配列和を全体の和から引く見方も補足しています。
  • AALC001 I - Subarray
    • 互いに重ならない連続部分列を 2 個まで選ぶ版を、長さ 00 の部分列も許したうえで、選ぶ個数と区間の端に接するかどうかで分けた 8 つの値をセグメント木に載せて、1 点更新と区間クエリに答えています。

素因数分解のリンク集

素因数分解について、参考になる記事や資料をまとめました。

素因数分解は、正の整数を素数の積で表すことです。1 つの整数 NN なら、2,3,4,…2, 3, 4, \dots で順に割れるだけ割っていき、i2>Ni^2 > N になったところで止めて、残った数が 11 より大きければそれも素因数に加える「試し割り」で O(N)O(\sqrt{N}) です。MM 以下の整数をたくさん素因数分解するなら、エラトステネスの篩で各整数の最小素因数(SPF)を前計算しておくと、1 個あたり素因数の個数(O(log⁡M)O(\log M))回の割り算で済みます。NN が 101810^{18} 程度まで大きいときは、Miller-Rabin 法で素数判定をしながら Pollard’s rho 法で約数を探すと、およそ O(N1/4)O(N^{1/4}) で分解できると期待できます(厳密な解析は未解決です)。

試し割りのループの条件は、sqrt を使わずに i * i <= N と整数で比べると誤差の心配がありません。ただし NN が 2312^{31} を超えうるなら、i も 64 bit 整数にしないと i * i があふれます。Miller-Rabin 法や Pollard’s rho 法で 101810^{18} 程度の数を扱うときは、法 NN での掛け算の途中の値が 64 bit に収まらないので、128 bit 整数(__int128)やモンゴメリ乗算を使います。Miller-Rabin 法の底は、64 bit 整数なら最初の 12 個の素数 2,3,5,…,372, 3, 5, \dots, 37 を使えば必ず正しく判定できます。底を少なく済ませると、強擬素数を素数と誤判定することがあります。AtCoder Library(ACL)には素因数分解の関数はありません。

  • AtCoder 版!マスター・オブ・整数 (素因数分解編)(drken、Qiita)
    • 素数判定、約数列挙、素因数分解を、どれも N\sqrt{N} までの試し割りで行う方法を C++ のコードつきで説明しています。割れるだけ割ると、割り切れる数が必ず素数になる理由や、最後に残った数が素数になる理由も丁寧に書かれています。後半は、約数の個数・約数の総和・オイラー関数の求め方と、素因数分解を考察に使う AtCoder の問題の解説、問題集です。
  • Integer factorization(cp-algorithms、英語)
    • 前半は試し割りと、その高速化(2・3・5 の倍数を飛ばす wheel factorization、篩で求めた素数だけで割る方法)です。後半はフェルマー法、Pollard の p−1p - 1 法、Pollard’s rho 法(Floyd と Brent の循環検出)を C++ のコードつきで説明しています。
    • rho 法のコードは約数を 1 つ見つけるだけで、素数判定と組み合わせて再帰的に分解する部分はありません。フェルマー法のコードは int を使っていて、nn が 2312^{31} に近いと a*a があふれます。

エラトステネスの篩と最小素因数(SPF)

Section titled “エラトステネスの篩と最小素因数(SPF)”
  • エラトステネスの篩の活用法を総特集! 〜 高速素因数分解・メビウスの反転公式 〜(drken、Qiita)
    • 篩の仕組みと O(Nlog⁡log⁡N)O(N \log\log N) の計算量を説明したあと、篩のついでに各整数の最小の素因数 minfactor を記録し、NN 以下の整数を 1 個あたり O(log⁡N)O(\log N) で素因数分解する方法を C++ の構造体で示しています。続けて、約数列挙、メビウス関数、高速ゼータ変換・メビウス変換、添字 GCD 畳み込みまで扱っています。
    • minfactor を求める最初のコード片は、戻り値の型が vector<bool> なのに return がありません。そのあとの構造体版のコードを使ってください。また、約数の個数を σ(n)\sigma(n) と書いていますが、ふつう σ(n)\sigma(n) は約数の和を表します。
  • 高速素因数分解(osa_k、日記)
    • 篩で各整数の最小の素因数を記録しておき、それで割ることを繰り返して素因数分解する方法を紹介し、素数で順に割る方法と 10710^7・10810^8 までの全整数で速さを比べています。競プロではこの方法が「osa_k 法」と呼ばれることがあります。
    • 本文の試し割りの計算量の見積もり(O(N+ln⁡N)O(N + \ln N) など)は、N\sqrt{N} まで調べれば十分であることを考えていない粗いものです。
  • Linear Sieve(cp-algorithms、英語)
    • 各合成数をその最小の素因数で 1 回だけ消す線形篩で、最小の素因数の配列を O(n)O(n) で求めます。正当性の証明つきです。実際の速さはふつうのエラトステネスの篩と同じくらいで、メモリは多く使うことにも触れています。
  • Sieve of Eratosthenes(cp-algorithms、英語)
    • 篩の実装と計算量の証明、n\sqrt{n} までで止める・奇数だけを扱うといった高速化のあと、「Segmented Sieve」と「Find primes in range」の節で区間篩を説明しています。後者は、R\sqrt{R} 以下の素数で区間 [L,R][L, R] の中の倍数を消していく方法で、R≈1012R \approx 10^{12}、R−L+1≈107R - L + 1 \approx 10^7 の例が挙げられています。
    • 扱っているのは区間内の素数の列挙だけで、区間内の各整数を素因数分解する方法には触れていません。

大きな数の素因数分解(Miller-Rabin 法・Pollard’s rho 法)

Section titled “大きな数の素因数分解(Miller-Rabin 法・Pollard’s rho 法)”
  • 素因数分解の高速なアルゴリズム(ロー法)(高校数学の美しい物語)
    • ロー法の手順と、誕生日のパラドックスをもとに N1/4N^{1/4} 回程度の反復で約数が見つかると期待できる理由を説明しています。厳密な解析が未解決であることも明記しています。コードはありません。
  • Primality tests(cp-algorithms、英語)
    • 試し割り、フェルマーテスト、Miller-Rabin 法を説明し、64 bit 整数を確実に判定できる底(7 個の底 2,325,9375,…2, 325, 9375, \dots または最初の 12 個の素数)を使った、__uint128_t による C++ の実装を載せています。素因数分解に使うときは、上の「Integer factorization」の rho 法と組み合わせます。
    • 最初の試し割りのコードは int で d * d を計算しているので、xx が 2312^{31} に近い素数のときにあふれます。

Miller-Rabin 法や Pollard’s rho 法を扱う講座はまだありません。

  • 素数の性質
    • O(N)O(\sqrt{N}) の素数判定から始め、素因数分解の一意性を証明し、O(N)O(\sqrt{N}) の試し割りによる素因数分解を Python で示しています。pp 進付値 vp(N)v_p(N) と、約数・最大公約数・最小公倍数を指数で言い換える方法も扱っています。後半は有理数の合同式とフェルマーの小定理です。
  • 素数篩
    • エラトステネスの篩、最小素因数の配列、線形篩、区間篩を、擬似コードと証明つきで説明しています。最小素因数を使うと 1 個あたり素因数の個数の回数で素因数分解でき、11 から NN まで全部分解しても O(Nlog⁡log⁡N)O(N \log\log N) であることを示し、約数の個数・約数の和・オイラーの φ\varphi 関数の列挙にも応用しています。区間内の整数をまとめて素因数分解できることには一言触れていますが、詳細は省略されています。関連問題の一覧つきです。
  • 素数に関する評価
    • 素数の個数や素数の逆数和などの評価を証明する講座です。「4.5. 素因数の個数」の節で、相異なる素因数の個数 ω(N)\omega(N) が O(log⁡N/log⁡log⁡N)O(\log N / \log\log N) であることを示しています。
  • Prime Factor (素因数分解)(Luzhiled’s Library)
    • O(n)O(\sqrt{n}) の試し割りで、素因数と指数の map を返す短い実装です。
  • 高速素因数分解(Miller Rabin/Pollard’s Rho)(Nyaan’s Library)
    • Miller-Rabin 法と Pollard’s rho 法による素因数分解と、素因数ごとの個数の map、約数列挙の関数があります。ドキュメントは Miller-Rabin 法の説明だけで、rho 法の節は未執筆(TODO)です。
    • n>262n > 2^{62} のときは exit(1) で終了します。101810^{18} までなら問題ありません。
  • fast-prime-factorization.hpp(Luzhiled’s Library)
    • 同じく Miller-Rabin 法と Pollard’s rho 法による 64 bit 整数の素因数分解で、モンゴメリ乗算を使っています。ドキュメントはなく、コードだけです。
  • 素因数分解(日本語版 Wikipedia)
    • 定義と一意性、試し割りと、大きな数向けのアルゴリズム(ρ 法、楕円曲線法、数体篩法など)の名前の一覧、一般の環での素元分解、大きな数の分解の記録を扱っています。各アルゴリズムの説明はありません。
  • ポラード・ロー素因数分解法(日本語版 Wikipedia)
    • Floyd の循環検出による元のアルゴリズムと、Brent の変形の擬似コード、n=8051n = 8051 の分解例があります。
    • 概念の節で擬似乱数として「線形合同法など」を挙げていますが、一次式では誕生日のパラドックスによる速さが得られません。使用例の節にあるとおり f(x)=x2+cf(x) = x^2 + c を使ってください。
  • ミラー–ラビン素数判定法(日本語版 Wikipedia)
    • 判定の根拠になる「11 の平方根は ±1\pm 1 だけ」という補題、アルゴリズム、Ruby のコード、誤判定の確率が 4−k4^{-k} 以下であることを説明しています。
    • 決定的に判定できる底の表は n<341,550,071,728,321n < 341{,}550{,}071{,}728{,}321 までしかなく、64 bit 整数全体での底は載っていません。それは英語版を見てください。
  • Pollard’s rho algorithm(英語版 Wikipedia)
    • 考え方、擬似コード、n=8051n = 8051 と n=10403n = 10403 の分解例、Brent の変形と、gcd をまとめて計算する高速化、計算量の見積もりがあります。
  • Miller–Rabin primality test(英語版 Wikipedia)
    • 強擬素数の考え方と証明、アルゴリズム、精度の評価に加えて、「Testing against small sets of bases」の節に、nn の範囲ごとに十分な底の一覧があります。n<264n < 2^{64} なら 2,3,5,…,372, 3, 5, \dots, 37 の 12 個で十分であることも書かれています。
  • アルゴリズムと数学 演習問題集 014 - Factorization:N≤1012N \le 10^{12} を試し割りで素因数分解して出力する基本問題です。
  • ABC169 D - Div Game:N≤1012N \le 10^{12} を素因数分解し、素因数ごとに指数を 1,2,3,…1, 2, 3, \dots と小さい順に使っていきます。
  • ABC280 D - Factorial and Multiple:K≤1012K \le 10^{12} を素因数分解し、素因数 pep^e ごとに N!N! が pep^e で割り切れる最小の NN を求めます。
  • CADDi 2018 C - Product and GCD:PP を素因数分解し、各素因数の指数を NN 個に均等に分けます。
  • ABC110 D - Factorization:MM を素因数分解し、素因数ごとに指数を NN 個の項へ配る方法を重複組合せで数えます。
  • ABC052 C - Factors of Factorial:11 から NN までを素因数分解して N!N! の各素因数の指数を足し合わせ、約数の個数を求めます。
  • ABC177 E - Coprime:10610^6 個の整数を最小素因数の前計算で素因数分解し、同じ素因数が 2 回現れるかを調べます。
  • ABC342 D - Square Pair:各要素から平方数の因子を取り除いた値を素因数分解で求め、それが等しい組を数えます。00 の扱いに注意します。
  • ABC227 G - Divisors of Binomial Coefficient:N≤1012N \le 10^{12} に対し、区間 [N−K+1,N][N - K + 1, N] の整数を区間篩でまとめて素因数分解します。
  • ABC412 E - LCM Sequence:1,…,n1, \dots, n の最小公倍数が変わるのは nn が素数のべきのときなので、区間篩で区間内の素数のべきを数えます。
  • Library Checker - Factorize:101810^{18} 以下の整数を最大 100100 個素因数分解します。Pollard’s rho 法の verify 用です。
  • Library Checker - Primality Test:101810^{18} 以下の整数を最大 10510^5 個素数判定します。Miller-Rabin 法の verify 用です。
  • Blitz Round #25 C - Root Value
    • 各 ai≤200a_i \le 200 を 200200 以下の 4646 個の素数で試し割りし、素数ごとの指数の累積和から区間の積の指数を求めて、その最大公約数を答えています。
  • DOJ Beginner Contest 11 G - Déjà vu
    • 操作を素数ごとの指数で考えて、すべての要素で指数が等しい素数だけが f(b)f(b) に残ることを示し、f(b)=cf(b) = c となる部分列の個数を cc の大きい順に求めています。
  • ShareOJ Programming Contest vol.1 B - One Digit Factorization
    • 1 桁の整数の積で表せることを素因数が 2,3,5,72, 3, 5, 7 だけであることに言い換え、N≤1018N \le 10^{18} をそれらで割れるだけ割って 11 が残るかで判定しています。

LIS のリンク集

LIS(最長増加部分列)について、参考になる記事や資料をまとめました。

LIS(Longest Increasing Subsequence)は、数列の部分列のうち増加しているもので最長のもの、またはその長さです。素直な DP は O(N2)O(N^2) ですが、「長さ kk の増加部分列の末尾として考えられる最小の値」を配列で持ち、各要素の置き場所を二分探索で求めると O(Nlog⁡N)O(N \log N) になります。また、「AiA_i で終わる増加部分列の最長の長さ」を値の座標についてのセグメント木や BIT で区間最大値として求める方法も O(Nlog⁡N)O(N \log N) で、重みつきの LIS や個数の数え上げに拡張しやすいです。

二分探索の方法では、狭義の増加(同じ値を許さない)なら lower_bound(Python では bisect_left)、広義の増加(同じ値を許す)なら upper_bound(bisect_right)を使います。資料によって「増加」がどちらを指すかが違うので注意してください。また、二分探索の方法で最後に残る配列は LIS そのものではありません。LIS を復元するには、各要素について直前の要素や、その要素で終わる LIS の長さを記録しておく必要があります。

  • LIS でも大活躍! DP の配列使いまわしテクニックを特集(けんちょん、Qiita)
    • ナップサック DP の配列の使いまわしから始めて、LIS の二分探索による方法とセグメント木による方法を、どちらも「DP の配列を使いまわしたもの」として説明しています。重みつきの LIS である EDPC Q - Flowers も扱っています。C++ です。
    • コードは lower_bound を使う狭義の LIS で、広義の場合の書き換えや復元には触れていません。
  • 最長増加部分列・最長共通部分列(いかたこのたこつぼ)
    • 二分探索による方法、復元、セグメント木による方法、増加部分列への最小の分解(Dilworth の定理)を、表で具体例を追いながら説明しています。狭義なら bisect_left、広義なら bisect_right を使うこと、セグメント木による方法で同じ値をどの順に処理するかも書かれています。後半は最長共通部分列(LCS)です。
    • 二分探索の Python のコードは、関数名(longest_increasing_subsequence)と呼び出し(lis(...))が食い違っているので、そのままでは動きません。また、コメントの「a以下の値が初めて出てくるindex」は「a以上」の誤りです。
  • LIS - 最長増加部分列(yamate11のブログ)
    • 長さだけを求める方法と、各要素の直前の要素の添字を記録して LIS を 1 つ復元する方法を、手順として短くまとめています。狭義なら lower_bound、広義なら upper_bound と明記されています。C++ です。
    • 添字の書き方に 0 始まりと 1 始まりが混ざっています。復元の最後の手順の「cj>0c_j > 0 なら」は「cj≥0c_j \ge 0 なら」と読んでください(先頭の要素 a0a_0 も直前の項になりえます)。
  • ABC354 F - Useless for LIS の公式解説(AtCoder)
    • 各要素で終わる LIS の長さと始まる LIS の長さを、値についてのセグメント木で求め、「両者の和から 11 を引いたものが LIS の長さに等しいか」で、その要素が LIS に含まれうるかを判定しています。セグメント木による方法の使い方の例として読めます。

2 つの値の両方が大きくなる列(箱の入れ子など)は、一方でソートしてからもう一方の LIS を求めることで解けます。このとき、1 つ目の値が同じものどうしがつながらないように、同じ値の中では 2 つ目の値の降順に並べるのが定番です。また、Dilworth の定理から、数列を狭義増加部分列に分けるときの最小の個数は、最長の広義減少部分列の長さに等しくなります。

  • ABC038 D - プレゼント のユーザ解説(seekworser、AtCoder)
    • 箱を ww の昇順、同じ ww では hh の降順に並べ、hh の LIS を求める、という 2 次元 LIS の定番の解き方を短く説明しています。
  • 競技プログラミングにおける最長部分増加列問題まとめ(はまやんはまやんはまやん)
    • LIS を使う問題を、入れ子構造に帰着するもの、広義の LIS を使うもの、3 次元のものなどに分けて並べた問題集です。解説は各問題への短いコメントだけです。
    • 2017 年の記事なので、AtCoder の問題へのリンクは古い形式の URL ですが、今の URL に転送されます。

LIS を扱う講座はまだありません。

  • bisect --- 配列二分法アルゴリズム(Python 公式ドキュメント)
    • bisect_left は等しい要素の左側、bisect_right は右側の位置を返します。狭義の LIS なら bisect_left、広義の LIS なら bisect_right です。key 引数は Python 3.10 で追加されました。LIS そのものには触れていません。
  • 最長増加部分列(LIS)(Competitive programming notebook)
    • bisect_left を使う長さの計算と、各要素で終わる LIS の長さを記録して後ろから復元する方法を、Python の短いコードで示しています。
    • 番兵の既定値が INF=10**9 なので、10910^9 を含む入力では長さを正しく数えられません。INF をもっと大きくしてください。
  • Longest Increasing Subsequence(最長増加部分列)(Luzhiled’s Library)
    • C++ の実装で、引数 strict で狭義(lower_bound)と広義(upper_bound)を切り替えられます。返すのは長さだけです。
  • dp/longest-increasing-sequence.hpp(Nyaan’s Library)
    • 狭義の LIS を 1 つ、添字の列で返す C++ の実装です。ファイル名は subsequence ではなく sequence です。ドキュメントはほとんどありません。
  • Longest increasing subsequence(英語版 Wikipedia)
    • O(nlog⁡n)O(n \log n) のアルゴリズムを、復元つきの擬似コードと具体例で説明しています。ほかに、LCS への帰着、Erdős–Szekeres の定理、ランダムな順列の LIS の長さが約 2n2\sqrt{n} になることなども載っています。日本語版の記事はありません。
    • 擬似コードは狭義の LIS ですが、本文では狭義か広義かを明記していません。
  • Longest increasing subsequence(cp-algorithms)
    • O(n2)O(n^2) の DP、二分探索による O(nlog⁡n)O(n \log n) の方法、セグメント木などのデータ構造による方法を、それぞれ復元の方法とあわせて説明しています(データ構造による方法の復元は省略)。広義の LIS、LIS の個数、増加しない部分列への最小の分解なども扱い、練習問題の一覧があります。
    • 広義の場合は「二分探索を少し変える」とだけ書かれています。upper_bound に変えればよいです。
  • Longest Increasing Subsequence(USACO Guide)
    • O(N2)O(N^2) と O(Nlog⁡N)O(N \log N) の方法、セグメント木による方法を説明し、交差しない線分の最大個数や増加部分列への最小の分解(Dilworth の定理)などの応用と問題の一覧があります。コードは Python で、狭義の LIS です。
  • Patience sorting(英語版 Wikipedia)
    • カードを山に積んでいくソートで、山の数が LIS の長さに等しくなります。二分探索による方法と同じ考え方で、山の間にポインタを張って LIS を復元する方法も書かれています。
    • 本文では「新しいカード以上の山に置く」、擬似コードでは「新しいカードより大きい山に置く」となっていて、狭義と広義が食い違っています。
  • Dilworth’s theorem(英語版 Wikipedia)
    • 半順序集合の最小の鎖分解の個数が最大の反鎖の大きさに等しいという定理と、その双対(Mirsky の定理)を証明つきで説明しています。LIS との関係は、Erdős–Szekeres の定理がこの定理の応用とみなせる、と一言触れているだけです。
  • Library Checker - Longest Increasing Subsequence:狭義の LIS を 1 つ、添字の列で出力します。復元の verify 用です。
  • CSES - Increasing Subsequence:狭義の LIS の長さを求める基本問題です。
  • ABC006 D - トランプ挿入ソート:動かさないカードが増加部分列になることに気づくと、NN から LIS の長さを引いたものが答えです。
  • 競プロ典型 90 問 060 - Chimera(★5):左からの LIS と右からの LIS を各位置で組み合わせて、増加してから減少する最長の部分列を求めます。
  • ABC038 D - プレゼント:縦・横ともに大きい箱にしか入れられない入れ子の段数を求める、2 次元 LIS の問題です。
  • ARC126 B - Cross-free Matching:共有点のない線分を最大個数選びます。片方の端点でソートすると、もう片方の LIS になります。
  • ABC134 E - Sequence Decomposing:数列を狭義増加部分列に分けるときの最小の個数を求めます。Dilworth の定理から、最長の広義減少部分列の長さです。
  • EDPC Q - Flowers:重みつきの LIS で、セグメント木や BIT で区間最大値を求めます。
  • ABC165 F - LIS on Tree:木の上の根からのパスごとの LIS を、DFS で二分探索の配列の変更を戻しながら求めます。
  • ABC354 F - Useless for LIS:各要素が LIS に含まれうるかを判定します。各要素で終わる LIS と始まる LIS の長さを使います。
  • ABC360 G - Suitable Edit for LIS:1 つの要素を好きな整数に置き換えたときの LIS の長さの最大値を求めます。
  • ABC237 F - |LIS| = 3:LIS の長さがちょうど 33 の数列を数えます。M≤10M \le 10 と小さいので、二分探索の方法で持つ配列そのものを DP の状態にできます。
  • DOJ Beginner Contest 11 F - Laboratory
    • 微生物を成長係数の順に並べたとき、xx 日目に選べる最大の種類数が、(個体数, 番号) の組の狭義の LIS の長さになることを使い、日数を二分探索しています。

転倒数のリンク集

転倒数について、参考になる記事や資料をまとめました。

数列 AA の転倒数は、i<ji < j かつ Ai>AjA_i > A_j を満たす組 (i,j)(i, j) の個数です。左から順に「自分より前にあって自分より大きい要素の個数」を BIT で数えて足していくと O(Nlog⁡N)O(N \log N) で求まります。マージソートの途中で、左半分と右半分にまたがる組を数える方法でも O(Nlog⁡N)O(N \log N) です。転倒数は、隣どうしの入れ替えで数列を昇順にするときの最小の回数(バブルソートの交換回数)に一致します。値の異なる隣どうしを入れ替えると転倒数はちょうど 11 増えるか 11 減り、昇順の列の転倒数は 00 だからです。

BIT を使う方法では値をそのまま添字にするので、値が大きいときや負の値があるときは座標圧縮が必要です。同じ値の組は転倒に数えないので、「自分以下の値の個数」を引くようにします。また、転倒数は最大で N(N−1)/2N(N-1)/2 になり、N=105N = 10^5 でも 32 bit 整数に収まらないので、答えは 64 bit 整数で持ってください。BIT そのものについては BIT のリンク集 も見てください。

  • 転倒数(pocala-kyopro、Scrapbox)
    • 例の数列で BIT に 1 を足していく様子を表で追いながら、「これまでに見た個数 − 自分以下の個数」で自分より前にある大きい値の個数が求まることを説明しています。C++ の実装つきです。
    • 値が 11 以上 NN 以下(順列)であることを前提にしていて、座標圧縮には触れていません。
  • BITで転倒数を求める(wisteria0410ss、Qiita)
    • BIT による方法を擬似コードで説明し、座標圧縮で BIT の長さを値の種類数に抑える方法も書いています。最後に、転倒数がバブルソートの交換回数に一致する理由を補足しています。
    • 擬似コードで、答えに tjt_j を足すだけの行に「BITを使ってO(log N)」というコメントがあります。BIT を使うのは 1 つ上の bb に 11 を足す行で、コメントの位置がずれています。
  • Binary Indexed Tree (BIT) 総まとめ!区間加算や二次元BITまで(アルゴリズムロジック)
    • BIT の記事の一節で、転倒数の手順を短くまとめています。値が 11 以上であることを前提にしているので、00 があるときは 11 を足すか座標圧縮してから使ってください。
  • 転倒数(taq225algo、Scrapbox)
    • 列を半分に分けて「左半分の転倒数 + 右半分の転倒数 + またがる組の数」で求める分割統治と、座標圧縮した BIT による方法の両方を、Python の実装つきで説明しています。
    • BIT の節の式 tk+1′=∑v<ak+1B[v]t'_{k+1} = \sum_{v < a_{k+1}} B[v] は、tj′t'_j の定義(ai≤aja_i \le a_j の個数)に合わせると v≤ak+1v \le a_{k+1} が正しいです。コードは正しく bit.sum(x+1) で、等しい値まで数えています。
  • Count Inversions of an Array(GeeksforGeeks、英語)
    • 全組を調べる O(n2)O(n^2) の方法と、マージソートでまたがる組を数える O(nlog⁡n)O(n \log n) の方法を、C++・Java・Python などのコードで示しています。
    • コードは転倒数を int で持っているので、そのまま使うと大きな nn であふれます。

転倒数そのものを扱う講座はまだありませんが、関連する講座があります。

  • 区間クエリのためのモノイド設計
    • 「8.1 転倒数」の節で、順列の転倒数を区間和のセグメント木で求める方法を 2 通り説明しています。添字の順に処理して値を添字にする方法と、値の順に処理して位置を添字にする方法です。一般の列のときの座標圧縮や、同じ値の扱いにも触れています。
  • inversion-counting.hpp(Nyaan’s Library)
    • 座標圧縮つきで転倒数を long long で返す inversion_counting と、隣どうしの入れ替えで列 vv を列 ww にする最小回数を返す swap_distance があります。ドキュメントはなく、コード中のコメントだけです。
  • Static Range Inversion Query(hitonanode’s library)
    • 数列の区間 [l,r)[l, r) の転倒数にオンラインで答える実装で、時間 O((N+Q)N)O((N + Q)\sqrt{N})、空間 O(NN)O(N\sqrt{N}) です。N=105N = 10^5 で約 128 MB 使うと書かれています。
  • 転倒 (数学)(日本語版 Wikipedia)
    • 転倒・転倒数・転倒ベクトルの定義と、置換の弱順序を扱う短い記事です。バブルソートや置換の符号との関係は書かれていません。
  • Inversion (discrete mathematics)(英語版 Wikipedia)
    • 転倒の定義、転倒集合、Lehmer code などの転倒を表すベクトル、4 文字の順列すべての表、置換の弱順序まで扱っています。比較ソートを改造すると O(nlog⁡n)O(n \log n) で数えられることにも一言触れています。
  • Point Update Range Sum(USACO Guide)
    • BIT とセグメント木の章の中に「Inversion Counting」の節があり、転倒数の問題の一覧もあります。C++ のコードは BIT ではなく、順序統計木(__gnu_pbds の tree)を使っています。
    • Java と Python のコードは値の上限 10710^7 の BIT をそのまま使っていて、座標圧縮はしていません。
  • chokudai_S001 J - 転倒数:順列をバブルソートしたときの交換回数を求める基本形です。
  • Library Checker - Static Range Inversions Query:区間の転倒数を答えるクエリを処理します。値は 10910^9 までなので座標圧縮が必要です。
  • ABC264 D - “redocta”.swap(i,i+1):各文字を atcoder での位置に置き換えると、順列の転倒数を求める問題になります。
  • ABC190 F - Shift and Inversions:先頭の要素を末尾に移したときの転倒数の変化を考え、すべての巡回シフトの転倒数を求めます。
  • ABC261 F - Sorting Color Balls:全体の転倒数から、同じ色どうしの転倒数を引きます。
  • ARC075 E - Meaningful Mean:累積和に直すと、l<rl < r かつ bl≤brb_l \le b_r となる組を数える問題になり、転倒数と同じく BIT で数えられます。
  • ARC136 B - Triple Shift:操作で転倒数の偶奇が変わらないことを使って判定します。同じ値があるときの扱いがポイントです。
  • ARC120 C - Swaps 2:Ai+iA_i + i に置き換えると隣接交換の問題になり、対応づけた順列の転倒数が答えです。
  • ARC088 E - Papple Sort:各文字の行き先を貪欲に決めたあと、行き先の順列の転倒数を数えます。
  • DOJ Beginner Contest 8 E - Swap Two Elements
    • 1 回の操作で転倒数がちょうど 11 しか変わらないことを示し、答えが転倒数になることをバブルソートで構成しています。
  • AALC001 D - Inversion Count
    • 値が 0,1,20, 1, 2 だけの列で、各値の個数と区間内の転倒数をセグメント木に載せ、1 点更新と区間の転倒数のクエリに答えています。

スライド最小値のリンク集

スライド最小値について、参考になる記事や資料をまとめました。

スライド最小値は、数列の上で長さ KK の窓を 1 つずつ右にずらしながら、各窓の最小値を求める手法です。deque(両端キュー)に添字を入れ、対応する値が単調増加になるように保ちます。新しい要素を入れる前に、末尾からその値以上の要素を捨て、窓から外れた添字は先頭から捨てます。すると deque の先頭が窓の最小値になります。各要素は 1 回入って高々 1 回出るだけなので、全体で O(N)O(N) です。窓の左端と右端がどちらも単調に動くなら、窓の幅が変わっても使えます。最大値のときは不等号を逆にします。

deque には値ではなく添字を入れると、先頭が窓から外れたかどうかを添字で判定できます。値だけを入れる実装もありますが、そのときは末尾から捨てるのを「より大きい」値に限り、同じ値を残す必要があります。また、窓の端が戻る(単調に動かない)区間最小値ならセグメント木やスパーステーブル、最小値以外の演算を窓の上でまとめたいなら、下で紹介する SWAG を使います。

  • スライド最大(最小)値・ヒストグラム内最大長方形問題を俯瞰する(kuuso1、Qiita)
    • 数値を戦闘力、窓に入ることを入学、出ることを卒業にたとえ、「番長の順番待ち」が deque で表せることを図で説明しています。添字を deque に入れる Python の実装があります。後半では、卒業のない場合としてスタックを使うヒストグラム内最大長方形問題を扱っています。
    • コードは最大値版だけです。
  • スライド最小値、SWAG(いかたこのたこつぼ)
    • 区間の値を求める手法(累積和、セグメント木、スパーステーブル、Mo’s Algorithm など)を表で比べたうえで、スライド最小値の deque の変化を具体例の表で追っています。後半は下の SWAG の説明で、Python の実装があります。例題は載っていません。

尺取り法・スライディングウィンドウとの関係

Section titled “尺取り法・スライディングウィンドウとの関係”
  • しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ(drken、Qiita)
    • しゃくとり法の解説記事です。「3-3. スライド最小値や Convex Hull Trick」の節で、区間の両端が単調に動くなら最小値を取る添字も単調に動くので、しゃくとり法のように処理できると説明しています。(値, 時刻) の組を deque に入れる C++ の SlideMin 構造体があります。
  • Sliding Window(USACO Guide、英語)
    • 前半は固定長の窓と、尺取り法による可変長の窓を sorted set で扱います。後半の「Sliding Window Maximum in O(N)O(N)」で、単調な deque(添字を持つ版と値を持つ版)と 2 つのスタックによるキューを説明しています。C++・Java・Python のコードと、問題の一覧があります。
    • 説明とコードは最大値版です。

スライド最小値は min や max にしか使えませんが、キューを 2 つのスタックで表し、それぞれのスタックで累積の値を持つと、結合法則を満たす任意の演算で「末尾に追加」「先頭を削除」「全体の値を求める」がならし O(1)O(1) でできます。これを SWAG と呼びます。

  • Foldable-Queue(SWAG) およびそのDeque版について(Shirotsume、Qiita)
    • 2 つのスタックでキューを作る方法、累積の値を持つスタック、それらを組み合わせた SWAG を順に説明しています。両端から出し入れできる Deque 版も扱っています。Python の実装があります。
  • Sliding Window Aggregation(data-structures、Scrapbox)
    • 操作と計算量、仕組みを短くまとめたページです。min については deque を使う別の方法(スライド最小値)があることにも触れています。参考文献と問題の一覧があります。

スライド最小値や SWAG を扱う講座はまだありません。窓の幅が固定でない区間最小値を求めたいときは、スパーステーブルの講座が参考になります。前計算 O(Nlog⁡N)O(N \log N) で、任意の区間の最小値に O(1)O(1) で答える方法です。

  • collections.deque(Python 公式ドキュメント)
    • deque は両端での追加と削除(append、appendleft、pop、popleft)がおよそ O(1)O(1) でできます。リストの pop(0) は O(n)O(n) なので、先頭から捨てる処理にはこちらを使います。添字によるアクセスは、両端なら O(1)O(1) ですが、中央付近では O(n)O(n) です。「deque のレシピ」の節には、窓の和を差分で更新する移動平均の例があります。
  • スライド最小値(Slide-Min)(Luzhiled’s memo)
    • C++ の実装で、slide_min(v, k) が長さ kk の各窓の最小値を返します。DP の高速化に使う例題の検証コードつきです。
  • Double-ended queue(英語版 Wikipedia)
    • 「Monotonic queue」の節で、単調な deque によるスライド最大値の O(n)O(n) の求め方を C++ のコードつきで説明し、DP の高速化や最小値つきのキュー(min-queue)にも触れています。スライド最小値だけの記事はなく、日本語版の「両端キュー」にはこの話はありません。
    • 最初のコード例は、引数の型が std::vector<int> &seq[] となっていて、そのままではコンパイルできません。
  • Minimum stack / Minimum queue(cp-algorithms)
    • 最小値つきのスタックとキューの作り方を説明しています。キューは、値だけを持つ deque、(値, 添字) を持つ deque、2 つのスタックの 3 通りです。最後に、固定長の窓の最小値がこれらで O(n)O(n) で求まることを示しています。C++ のコード断片で、値は int です。
  • Competitive Programmer’s Handbook(Antti Laaksonen、PDF)
    • 8 章「Amortized analysis」の 8.3 節「Sliding window minimum」で、8.2 節の「最も近い小さい要素」をスタックで求める方法と同じ考え方として、キューの変化を図で説明しています。コードはありません。
  • yukicoder contest 517 D - Streaming Schedule
    • 「休む日」についての DP の遷移を累積和で変形し、長さ C−1C - 1 の窓の最大値を deque によるスライド最大値で求めています。deque に添字ではなく値を入れる実装です。

強連結成分分解のリンク集

強連結成分分解について、参考になる記事や資料をまとめました。

強連結成分分解(SCC)は、有向グラフの頂点を「互いに行き来できる頂点どうし」のグループ(強連結成分)に分けることです。各成分を 1 つの頂点に縮約すると、閉路のない有向グラフ(DAG)になるので、その上でトポロジカル順に DP などができるようになります。DFS を 2 回行う Kosaraju 法や、DFS を 1 回行い lowlink を使う Tarjan 法で、O(N+M)O(N + M) で求められます。2-SAT もこれを使って解きます。

成分を並べる順序には注意が必要です。AtCoder Library(ACL)の scc_graph::scc() は成分をトポロジカル順(辺の始点側の成分が先)に返しますが、Tarjan 法をそのまま書くと成分は逆トポロジカル順に見つかります。自分で書いたり他のライブラリを使ったりするときは、どちらの順かを確かめてください。また、1 頂点だけの成分は、自己ループがなければ閉路を含みません。DFS を再帰で書くと、頂点数が多いときに再帰が深くなりすぎることがあります。

  • 強連結成分分解の意味とアルゴリズム(高校数学の美しい物語)
    • 定義と、元のグラフで DFS をして帰りがけ順に番号を付け、辺を逆向きにしたグラフで番号の大きい頂点から DFS する手順(Kosaraju 法)を、図と具体例で説明しています。正しさの証明もありますが概略で、途中の補題は省略されています。コードはありません。
  • AtCoder Library Practice Contest G - SCC(けんちょんの競プロ精進記録)
    • 強連結成分分解とは何か、縮約すると DAG になる理由を図で説明し、ACL を使うコードと、DFS を 2 回行う自前の C++ 実装(縮約した DAG も作る)を載せています。
  • 強連結成分(SCC)(technical-note)
    • Kosaraju 法の手順を、DFS で番号を付けるところから成分を 1 つずつ取り出すところまで、図で 1 ステップずつ追っています。「上流・下流」のたとえで正しさを直感的に説明していて、厳密な証明やコードはありません。
  • 競技プログラミングにおける有向グラフに関する問題まとめ(はまやんはまやんはまやん)
    • トポロジカルソート、強連結成分分解、DAG の最小パス被覆、区間に辺を張る方法など、有向グラフの手法と、それを使う問題をまとめています。説明は短く、解説は外部の記事へのリンクが中心です。2017 年の記事です。
  • 2-SAT(cp-algorithms、英語)
    • 節 (a∨b)(a \lor b) を ¬a⇒b\lnot a \Rightarrow b と ¬b⇒a\lnot b \Rightarrow a の 2 本の辺にした含意グラフを作り、xx と ¬x\lnot x が同じ成分にあるかで判定し、成分のトポロジカル順の番号から割り当てを決める方法を、証明つきで説明しています。C++ の実装もあります。
    • 実装の最後の使用例 example_usage にある vector<bool>(True, False, True) は C++ として正しくないので、そこはそのまま写さないでください。

強連結成分分解そのものを扱う講座はまだありません。関連する講座として、次のものがあります。

  • グラフ理論用語集
    • 5 章で強連結成分と強連結グラフを、9 章で DAG とトポロジカルソートを定義しています。DAG であることは、すべての強連結成分が 1 頂点からなりループを持たないことと同値だ、とも書かれています。
  • トーナメント
    • 5 章で、トーナメント(どの 2 頂点の間にもちょうど 1 本の向きつきの辺がある有向グラフ)では強連結成分が一列に並び、強連結成分分解が各頂点の入次数だけから決まることを示しています。
  • scc(AtCoder Library のドキュメント)
    • scc_graph に add_edge で辺を追加し、scc() で成分ごとの頂点のリストを受け取ります。成分はトポロジカル順に並び、成分の中の頂点の順序は決まっていません。計算量は O(n+m)O(n + m) です。
  • two_sat(AtCoder Library のドキュメント)
    • 節 (xi=f)∨(xj=g)(x_i = f) \lor (x_j = g) を add_clause で追加し、satisfiable() で判定、answer() で割り当てを受け取ります。内部では強連結成分分解を使っています。
  • Strongly Connected Components (強連結成分分解)(Luzhiled’s Library)
    • Tarjan 法の C++ 実装で、各頂点の成分番号 comp(トポロジカル順に振り直してある)、成分ごとの頂点 group、縮約した DAG dag が得られます。DFS は再帰を使わずに書かれています。
  • 強連結成分(日本語版 Wikipedia)
    • 定義、縮約すると DAG になること、Kosaraju 法・Tarjan 法・経路ベースの方法、並列化向けの方法を短く紹介しています。擬似コードはなく、各方法の説明は数文です。
  • Strongly connected component(英語版 Wikipedia)
    • 日本語版と同じ範囲に加えて、2-SAT や Dulmage–Mendelsohn 分解への応用にも触れています。
  • Tarjan’s strongly connected components algorithm(英語版 Wikipedia)
    • Tarjan 法の擬似コードと計算量の説明があります。成分が逆トポロジカル順に出力されることや、lowlink の更新方法に原論文と違う変種があることも書かれています。
  • 強連結成分分解(Kyopro Encyclopedia of Algorithms)
    • 定義、計算量、縮約すると DAG になることを短くまとめた辞典の項目です。DFS を 2 回行う方法と lowlink を使う方法の参考として、上の高校数学の美しい物語の記事と ACL が挙げられています。
  • Strongly Connected Components and Condensation Graph(cp-algorithms)
    • Kosaraju 法と Tarjan 法の両方を、証明と C++ 実装つきで説明しています。縮約したグラフの作り方と、Kosaraju 法では成分がトポロジカル順、Tarjan 法では逆トポロジカル順に得られることも書かれています。
    • 実装は再帰の DFS で、縮約したグラフには多重辺が残ります。
  • Strongly Connected Components(USACO Guide)
    • Kosaraju 法と Tarjan 法の実装と、後半に 2-SAT の節があります。SCC と 2-SAT それぞれの問題の一覧もあります。
  • ABC478 E - lt and le
    • 不等式の条件を辺にしたグラフを強連結成分分解し、< の辺の両端が同じ成分にあれば No、なければ成分のトポロジカル順の番号をそのまま答えにしています。本番では嘘解法で通してしまった話も書いています。
  • ShareOJ Programming Contest vol.1 E - Solicitation of Murder
    • 外から入る辺のない成分に生存者が必ず残ることを示し、成分ごとに独立に数えて掛け合わせています。

ダイクストラ法のリンク集

ダイクストラ法について、参考になる記事や資料をまとめました。

ダイクストラ法は、辺の重みがすべて非負のグラフで、1 つの始点から各頂点への最短距離を求めるアルゴリズムです。「まだ確定していない頂点のうち、暫定の距離が最小のもの」を確定させ、そこから出る辺で隣の頂点の距離を更新する、という操作を繰り返します。優先度付きキュー(二分ヒープ)を使うと O((V+E)log⁡V)O((V + E) \log V)、ヒープを使わずに毎回最小の頂点を探すと O(V2)O(V^2) です。負の重みの辺があると正しく動かないので、そのときはベルマン-フォード法などを使います。

競プロでよく書く実装では、距離を更新するたびに (距離, 頂点) をキューに追加し、古い要素は消さずに残します。そのため、取り出した距離が記録している距離より大きいときは読み飛ばす処理(if d > dist[v]: continue)が必要です。これがないと計算量が悪化します。また、距離は 64 bit 整数で持つ必要があることが多いです。

AtCoder Library(ACL)にはダイクストラ法がなく、AtCoder Algorithm Lectures にも今のところ最短経路の講座はありません。

  • 最短経路問題総特集!!!BFSから拡張ダイクストラまで(ageprocpp、Qiita)
    • BFS、ベルマン-フォード法、ダイクストラ法、ワーシャル-フロイド法、経路復元、拡張ダイクストラ(頂点を増やしたグラフ上のダイクストラ法)までを、文章で順に説明しています。ダイクストラ法の手順には、古い要素を読み飛ばす処理も書かれています。コードはほとんどありません。
    • ワーシャル-フロイド法の節の「途中で辺の長さが変わるクエリがあっても O(V2)O(V^2) で対応できる」は、辺が短くなる場合に限った話です。
  • ダイクストラ法による単一始点最短経路を求めるアルゴリズム(アルゴリズムロジック)
    • 手順、計算量、C++ の実装、経路復元、正当性の考え方を、図を使って説明しています。
    • キューに入れる距離の型が pair<long, int> の long です。AtCoder では 64 bit ですが、Windows などでは 32 bit なので、書き写すときは long long にしてください。
  • ダイクストラ法・ダイクストラ法の高速化(アルゴ式)
    • 問題を解きながら手順を学ぶ形式です。まずヒープを使わない O(N2+M)O(N^2 + M) の方法を実装し、次の問題でヒープを使って高速化します。
  • ダイクストラ法のよくあるミスと落し方(snuke)
    • 古い要素を読み飛ばす処理を忘れる、最大ヒープのまま使う、負の辺のあるグラフに使う、といったよくあるミスで、実際にどれだけ遅くなるかを撃墜ケースつきで説明しています。自分の実装を確かめるのに役立ちます。
  • Dijkstra 法(Kyopro Encyclopedia of Algorithms)
    • 定義、計算量、高速化の要点(キューに入れる前の枝刈り、0-1 BFS、拡張したグラフでの利用など)を短くまとめた辞典の項目です。
  • 色々なダイクストラ高速化(yosupo、スライド)
    • キューに入れる前の枝刈り、辺の重みが 0/10/1 のときの 0-1 BFS、重みが小さい整数のときの方法、Radix Heap などの高速化を紹介しています。C++ です。
  • 01-BFSのちょっと丁寧な解説(ARMERIA)
    • ダイクストラ法、BFS、01-BFS を「暫定の距離が最小の頂点を取り出す」という共通点から説明しています。C++ と Python のコードがあります。
  • heapq --- ヒープキューアルゴリズム(Python 公式ドキュメント)
    • heapq は最小ヒープで、(距離, 頂点) のタプルをそのまま入れられます。「優先度キュー実装の注釈」の節では、優先度が変わった要素に無効の印をつけて残し、新しい要素を追加し直す方法を紹介しています。ダイクストラ法で古い要素を読み飛ばすのと同じ考え方です。
  • Dijkstra (単一始点最短路)(Luzhiled’s Library)
    • C++ の実装で、距離に加えて、直前の頂点と辺の番号を返すので経路復元にも使えます。距離の型はテンプレート引数なので、long long を指定してください。
  • Yosupo Library Checker - Shortest Path(けんちょんの競プロ精進記録)
    • 下の Library Checker の問題の解説で、ダイクストラ法での経路復元の方法を説明しています。C++ のテンプレートつきです。
  • ダイクストラ法(日本語版 Wikipedia)
    • 擬似コード、ヒープの種類ごとの計算量、ビー玉と紐のたとえによる説明があります。擬似コードはキューの中の値を書き換える(decrease-key)形で、競プロでよく書く「追加して読み飛ばす」形とは違います。
  • Dijkstra’s algorithm(英語版 Wikipedia)
    • 歴史、擬似コード、正当性の証明、計算量、双方向ダイクストラ法などの変種まで載っています。キューに追加して読み飛ばす形の実装にも触れています。
  • Dijkstra - finding shortest paths from given vertex・Dijkstra on sparse graphs(cp-algorithms)
    • 前者はヒープを使わない O(n2+m)O(n^2 + m) の方法を正当性の証明と経路復元つきで、後者は set と priority_queue を使う O(mlog⁡n)O(m \log n) の方法を説明しています。後者には、読み飛ばす処理がないと O(nm)O(nm) まで悪化しうることも書かれています。
    • コードは距離を int で持っています。また、後者でフィボナッチヒープを使った O(nlog⁡n+m)O(n \log n + m) を「理論上の下限」としているのは、比較に基づく方法に限った話です。
  • Shortest Paths with Non-Negative Edge Weights(USACO Guide)
    • 後半がダイクストラ法の節で、C++・Java・Python の実装と問題の一覧があります。読み飛ばす処理を外すと TLE する例も説明しています。前半はベルマン-フォード法とワーシャル-フロイド法です。
  • ABC477 E - Wheel Distance
    • 中心の頂点から各頂点への最短距離をダイクストラ法で前計算し、各クエリに場合分けで答えています。

累積和・いもす法のリンク集

累積和といもす法について、参考になる記事や資料をまとめました。

累積和は、数列 a0,…,aN−1a_0, \dots, a_{N-1} に対して S0=0S_0 = 0、Si+1=Si+aiS_{i+1} = S_i + a_i を前計算しておき、区間 [l,r)[l, r) の和を Sr−SlS_r - S_l で O(1)O(1) で求める手法です。2 次元に広げると、長方形の範囲の和も 4 つの値の足し引きで求められます。

いもす法は、その逆の操作です。「区間 [l,r)[l, r) に xx を足す」を ll に +x+x、rr に −x-x と記録するだけで済ませ、最後に累積和をとって全体の値を一度に求めます。2 次元(長方形への加算)や、木の上(部分木への加算)にも使えます。

資料によって、区間を半開区間 [l,r)[l, r) で書くものと閉区間 [l,r][l, r] で書くものがあります。読み比べるときは、どちらの流儀かに気をつけてください。

  • 累積和を何も考えずに書けるようにする!(けんちょん、Qiita)
    • 半開区間と S0=0S_0 = 0 の流儀で 1 次元の累積和を丁寧に説明し、2 次元の累積和まで扱っています。例題 5 問の C++ の解答つきで、最後にいもす法やしゃくとり法などの発展の話題も紹介しています。
    • 2-1 節の検算で「s13=a1+⋯+a12s_{13} = a_1 + \dots + a_{12}」のように添字が 1 ずれています(定義どおりなら a0a_0 からの和です)。差をとった結果は正しいです。
  • 区間の和を求めるアルゴリズム(区間の更新なし)(アルゴリズムロジック)
    • 1 次元の累積和を、図を多く使って初心者向けに説明しています。C++ の実装と練習問題つきです。
  • 二次元での区間和を求めるアルゴリズム(区間の更新なし)(アルゴリズムロジック)
    • 2 次元の累積和の作り方と長方形の和の求め方を、たくさんの図で説明しています。
    • 最後の「更新がある場合」で 2 次元 BIT の計算量を O(log⁡HW)O(\log HW) としていますが、正しくは O(log⁡Hlog⁡W)O(\log H \log W) です。

コードは int で書かれているものが多いので、和が大きくなる問題では long long を使ってください。

  • いもす法(いもす研)
    • 考案者のいもすさんによる解説です。1 次元の基本から、2 次元、三角形・六角形の座標系、高次(2 次関数など)まで、図を多く使って説明しています。コードは C/C++ で、区間は半開区間です。英語版もあります。
    • 区間の右端 EiE_i が TT になり得るのに、配列を大きさ TT で扱っています。書き写すときは、配列を 1 つ大きく取ってください。
    • 2 次元の説明で、(Ai,Di)(A_i, D_i) を「右上」、(Bi,Ci)(B_i, C_i) を「左下」と呼んでいますが、コードの座標の向きでは逆です。どちらも −1-1 を足す点なので、結果は変わりません。
  • Pythonで累積和・累積積(itertools.accumulate)(note.nkmk.me)
    • itertools.accumulate の使い方の解説です。initial=0 を指定すると先頭に 00 がついた長さ N+1N + 1 の累積和になること、max や operator.mul を渡して累積 max や累積積を作れることが分かります。

木の上のいもす法を一般的に解説した定番の記事は見つからなかったので、問題の解説記事を挙げます。

  • AtCoder ABC 138 D - Ki(けんちょんの競プロ精進記録)
    • 部分木全体への加算を、根の頂点に記録しておき、最後に根から子へ値を配ることで O(N+Q)O(N + Q) にする方法です。配列のいもす法から順に木へ移していく流れで説明しています。コードは C++ の再帰 DFS です。
  • AtCoder ABC 187 E - Through Path(けんちょんの競プロ精進記録)
    • 「部分木の外への加算」を「全体に足して、部分木から引く」に言い換えて、上と同じ方法に帰着させています。
  • いもす法のカテゴリ(けんちょんの競プロ精進記録)
    • いもす法を使う問題の解説がまとまっていて、問題集としても使えます。

累積和・いもす法そのものを解説した講座はありません。

  • 転置原理入門
    • 転置原理の講座で、具体例として区間和クエリ(累積和)の解法を転置すると、区間加算クエリの解法が得られることを示しています。5.4 節で、それが imos 法であると紹介しています。累積和といもす法の関係を知りたい人向けの発展的な読み物で、累積和は前提知識として扱われています。
  • 累積和(日本語版 Wikipedia)、Prefix sum(英語版 Wikipedia)
    • 定義と、inclusive scan・exclusive scan の違い、並列計算での求め方が中心です。区間和を求める使い方の説明はほとんどないので、用語を確かめる程度に使ってください。いもす法(差分配列)の記事は日本語版・英語版ともにありません。
  • Summed-area table(英語版 Wikipedia)
    • 2 次元の累積和の記事で、画像処理(integral image)の文脈で書かれています。dd 次元への一般化の式も載っています。dd 次元の段落では、2 次元の段落と点の名前の付け方が入れ替わっています。
  • Introduction to Prefix Sums(USACO Guide)
    • 1 次元の累積和の入門で、C++・Java・Python のコードと練習問題の一覧があります。
    • 最初の Python のコードは psums[-1] を psum[-1] と書き間違えていて、そのままでは動きません。
  • More on Prefix Sums(USACO Guide)
    • 最大部分配列和、2 次元の累積和(構築の様子が見られる図つき)、差分配列(いもす法)を扱っています。区間は閉区間で書かれています。
  • An Introduction To Difference Arrays(arujbansal、Codeforces)
    • 1 次元の差分配列の短い入門です。閉区間 [L,R][L, R] で書いていて、配列を N+2N + 2 の大きさで取る理由も説明しています。

Union-Find のリンク集

Union-Find について、参考になる記事や資料をまとめました。

Union-Find(素集合データ構造、DSU)は、互いに交わらない集合の族を管理し、「2 つの集合を併合する」「2 つの要素が同じ集合にあるか判定する」をほぼ定数時間で行えるデータ構造です。各集合を根つき木で表し、経路圧縮と union by size(または union by rank)の両方を使うと、1 回の操作がならし O(α(n))O(\alpha(n)) になります(α\alpha は逆アッカーマン関数)。片方だけでも、ならし O(log⁡n)O(\log n) です。

  • Union find(素集合データ構造)(AtCoder、スライド)
    • AtCoder Typical Contest 001 の B - Union Find の解説スライドです。集合を木で表す考え方から、経路圧縮・ランクによる高速化と C++ 実装までを図を中心に短く説明しています。
    • 実装では配列名に rank を使っているので、using namespace std; と一緒に書き写すと std::rank と名前がぶつかることがあります。
  • Union-Find Tree を理解する!素集合系を扱うデータ構造(アルゴリズムロジック)
    • 素朴な実装から、経路圧縮、union by rank・union by size へと段階的に改良していく解説です。両方の C++ 実装と練習問題がそろっています。
  • PythonでのUnion-Find(素集合データ構造)の実装と使い方(note.nkmk.me)
    • Python での実装を段階的に作っていく記事です。グループの列挙などの便利なメソッドつきのクラスも載っています。
    • 途中に出てくる経路圧縮だけの版は、要素数が多いと再帰の上限に当たることがあります。最後の完成形(union by size つき)なら問題ありません。
  • dsu のドキュメント
    • 公式の仕様です。merge は新しい代表元を返し、groups で連結成分をまとめて取り出せます。実装は union by size と経路圧縮の併用です(ソースのコメントに書かれています)。
  • Union-Find の計算量上界
    • 経路圧縮と union by size を併用したときの計算量が O(N+Qα(N))O(N + Q\alpha(N)) であることを証明する講座です。上級者向けです。
  • アッカーマン関数,逆アッカーマン関数
    • 上の講座の準備として、アッカーマン関数と逆アッカーマン関数の定義と、文献ごとの定義の違いを整理しています。
  • Union Find(Luzhiled’s Library)
    • 短くて読みやすい C++ 実装で、各関数の計算量が日本語で書かれています。同じライブラリに、重み付き、undo 付き、部分永続などの派生版もあります。
    • 部分永続版のドキュメントは find を O(α)O(\alpha) としていますが、経路圧縮をしていないので、実際は O(log⁡n)O(\log n) です。
  • Disjoint-set data structure(英語版 Wikipedia)
    • 経路圧縮・path halving・path splitting と union by size/rank の擬似コード、片方だけ使ったときと両方使ったときの計算量、歴史や変種まで網羅しています。右上の表の Search の最悪計算量が O(α(n))O(\alpha(n)) になっていますが、本文にあるとおり 1 回あたりの最悪は Θ(log⁡n)\Theta(\log n) です。
  • 素集合データ構造(日本語版 Wikipedia)
    • 英語版の古い版をもとにした短い記事で、基本操作と union by rank・経路圧縮の擬似コードを日本語で確認できます。経路圧縮だけを使ったときの計算量は載っていません。
  • Disjoint Set Union(cp-algorithms)
    • 基本に加えて、偶奇つき Union-Find による二部グラフ判定、区間塗りのオフライン処理など、応用を幅広くまとめています。
  • ABC478 E - lt and le
    • 公式解説の方針を紹介する節で、同じ値になる頂点のグループを DSU でまとめています。

Cartesian Tree のリンク集

Cartesian Tree について、参考になる記事や資料をまとめました。

Cartesian Tree は、数列の最小値を根にし、その左側と右側の部分列から左右の部分木を再帰的に作った二分木です(最大値を根にする流儀もあります)。添字について見ると二分探索木、値について見るとヒープになっています。スタックを使えば O(N)O(N) で構築できます。「区間を最小値で分割して再帰する」分割統治は、この木の上の再帰とみなせます。

同じ値があるときは、どちらを小さいとみなすかで木の形が変わります。下の資料の多くは左端の最小値を根にしていますが、右端を根にするものもあるので注意してください。

区間最小値(RMQ)は、Cartesian Tree の上の 2 頂点の最小共通祖先(LCA)に対応します。

  • 前処理O(n)クエリO(1)のLCAと静的RMQ(joisino)
    • RMQ を Cartesian Tree の上の LCA に帰着させ、前処理 O(n)O(n)・クエリ O(1)O(1) を実現する記事です。スタックによる構築も図で説明しています。
  • Solve RMQ by finding LCA(cp-algorithms、英語)
    • RMQ が LCA に帰着できることの説明と、スタックによる構築のコードがあります。このコードでは、同じ値があると右端の最小値が根になります。
  • LCA and RMQ 簡潔もあるよ!(井上祐馬、スライド)
    • RMQ から LCA への帰着から、簡潔データ構造まで扱う上級者向けの資料です。

Cartesian Tree を扱う講座はまだありません。

  • Cartesian Tree(Nyaan’s Library)
    • 日本語のドキュメントつきの実装です。同じ値があるときは左端の最小値を根にすると明記されています。戻り値は子のリストと根の組で、左右の子は区別されません。

百科事典・英語・中国語の資料

Section titled “百科事典・英語・中国語の資料”
  • Cartesian tree(英語版 Wikipedia)
    • 定義と同じ値の扱い、線形時間の構築法をいくつか、RMQ・LCA や Treap との関係までを網羅しています。日本語版の記事はありません。
  • 笛卡尔树(OI Wiki、中国語)
    • 右端の鎖を単調スタックで管理する O(n)O(n) 構築を図とコードで説明し、ヒストグラム中の最大長方形への応用を例題として扱っています。
  • Treap (Cartesian tree)(cp-algorithms、英語)
    • ロシア語圏などでは Treap のことも Cartesian tree と呼ぶため、この記事の題に入っています。中身は Treap の解説で、数列から作る Cartesian Tree の説明ではありません。

BIT のリンク集

BIT(Binary Indexed Tree、Fenwick Tree)について、参考になる記事や資料をまとめました。

BIT は、列に対して「1 点への加算」と「先頭からの和(prefix 和)の取得」をどちらも O(log⁡N)O(\log N) で行えるデータ構造です。区間 [l,r)[l, r) の和は、2 つの prefix 和の差で求まります。セグメント木よりできることは少ないものの、実装が短く高速です。BIT を 2 本使った区間加算や、BIT 上の二分探索(累積和が ww 以上になる最初の位置を O(log⁡N)O(\log N) で求める)もよく使われます。

  • Binary Indexed Tree のはなし(hos、JOI 春合宿 2014 の講義スライド)
    • BIT の動きを図で 1 ステップずつ追いながら、1 点加算・prefix 和、区間加算、2 次元 BIT、BIT 上の二分探索まで解説しています。日本語の BIT 解説の定番です。
    • p.75 の二分探索の擬似コードの「n 以下の最小の 2 ベキ」は「最大」の誤りです。
  • Binary Indexed Tree (BIT) 総まとめ!区間加算や二次元BITまで(アルゴリズムロジック)
    • 1 点加算・区間和から、BIT 2 本による区間加算、BIT 上の二分探索、転倒数、2 次元 BIT までを図と C++ のコードでまとめています。練習問題も付いています。
    • 転倒数の手順は、値が 1 以上であることを前提にしています。値に 0 があるときは、1 を足すか座標圧縮してから使ってください。
  • fenwick_tree のドキュメント
    • 公式の仕様です。0-indexed で、区間和は半開区間 [l,r)[l, r) で求めます。BIT 上の二分探索はありません。

BIT を扱う講座はまだありません。

  • Binary Indexed Tree(Fenwick Tree)(ikatakos)
    • Python の実装集です。区間加算(BIT 2 本)、累積和の二分探索、BIT に載せられる演算の条件、座標圧縮や辞書を使った BIT、2 次元 BIT まで扱っています。
    • 区間加算版の sum に : の抜けがあり、演算を渡せる版の lower_bound はそのままでは動きません。通常版の Bit.lower_bound は正しく動きます。
  • Binary Indexed Tree(Luzhiled’s Library)
    • BIT 上の二分探索 lower_bound・upper_bound を備えた実装です。1 点加算は apply、区間和は prod という名前です。
  • Fenwick Tree(data-structures)
    • BIT でできる操作を、可換モノイドの場合とアーベル群の場合に分けて整理しています。参考資料や実装へのリンクもまとまっています。
  • Fenwick tree(英語版 Wikipedia)
    • 同じ配列を、部分和用・更新用・二分探索用の 3 つの木として見ることで、BIT の構造を説明しています。
  • フェニック木(日本語版 Wikipedia)
    • 英語版の古い版をもとにした短い記事で、細かい誤りがあります。たとえば多次元の場合の計算量が O(4dlog⁡dn)O(4^d \log_d n) になっていますが、引用元では O(4dlog⁡dn)O(4^d \log^d n) です。
  • Fenwick Tree(cp-algorithms)
    • 0-indexed と 1-indexed の両方の実装、2 次元 BIT、BIT 2 本による区間加算・区間和まで扱っています。練習問題も多く載っています。

セグメント木のリンク集

セグメント木について、参考になる記事や資料をまとめました。

セグメント木は、列に対して「1 点の更新」と「区間の積(和・最小値・最大値など)の取得」をどちらも O(log⁡N)O(\log N) で行えるデータ構造です。演算が結合法則を満たし、単位元を持つ(モノイドである)ことが条件です。区間に対する更新も行えるように拡張したものを、遅延評価セグメント木(遅延セグ木)と呼びます。区間 chmin のように遅延セグ木にそのままでは載らない作用を扱うための拡張に、Segment Tree Beats があります。

セグメント木そのものを解説する講座はまだありませんが、関連する講座があります。

  • 区間クエリのためのモノイド設計
    • 区間の情報をどう持ち、どう結合するかを、区間和・区間最小値から関数合成・行列まで例を挙げて解説しています。セグメント木を使ったことがある人向けです。
  • 代数構造用語集
    • モノイドなどの用語の定義です。
  • 永続セグメント木
    • 過去の状態を残したまま更新できるようにしたセグメント木です。
  • セグメント木(Wikipedia)
    • 前半は Bentley による元々の segment tree(線分の集合を格納し、ある点を含む線分を列挙する木)の説明で、競プロで使うものとは別物です。モノイドへの一般化と配列による実装は後半にありますが、細かい誤りがあるので、ほかの資料と合わせて読むのがおすすめです。
  • Segment Tree(cp-algorithms)
    • 英語の定番の解説です。応用例が多く載っています。