コンテンツにスキップ

ブログ

repovive starter round 10 C - Museum Records

nn 人が博物館に 1 回ずつ入って出ました。2n2n 回の入退場の時刻はすべて異なります。各人 ii について、

  • aia_i:ii が入る前に出ていた人数
  • bib_i:ii が出たあとに入ってきた人数

が記録されています。すべての記録が正しくなる入退場の順番があるか判定する問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、0≤ai,bi<n0 \le a_i, b_i < n)。

aia_i は、入るのが遅い人ほど大きいか等しいです。よって、入る順番は aia_i の昇順です。aia_i が等しい人どうしの間では誰も出ていないので、その人たちの入る順番を入れ替えても、ほかの人の a,ba, b は変わりません。

kk 人目が入ってから k+1k + 1 人目が入るまでの間を「すき間 kk」と呼びます(すき間 nn は最後の人が入ったあと)。bib_i 人があとから入ってくるので、人 ii はすき間 n−bin - b_i で出ます。同じすき間で出る人どうしの順番は、記録に影響しません。

こうして入退場の順番は(記録に影響しない入れ替えを除いて)決まるので、次の 2 つを満たすか調べれば十分です。人 ii が kik_i 番目に入るとします。

  1. 入ってから出る:ki≤n−bik_i \le n - b_i。
  2. aia_i が正しい:aia_i は、n−bj≤ki−1n - b_j \le k_i - 1 である人 jj の人数に等しい。

aia_i が等しい人どうしの順番は 2. に影響しないので、1. を満たしやすい順にします。それは bib_i の大きい人(早く出る人)を先にする順です。

aia_i の昇順、同じなら bib_i の降順に並べます。0-indexed で ii 番目の人は k=i+1k = i + 1 番目に入るので、1. は i+1≤n−bi + 1 \le n - b です。

また、2. の人数は、すき間ごとに出る人数を数えて累積和をとれば求まります。ckc_k を「すき間 kk 以下で出る人数」とすると、2. は a=cia = c_i です。

全員がこの 2 つを満たせば Yes、そうでなければ No です。計算量はソートの O(nlog⁡n)O(n \log n) です。

Python
n = int(input())
ab = [tuple(map(int, input().split())) for i in range(n)]
ab.sort(key=lambda x: (x[0], -x[1]))
c = [0] * (n + 1)
for a, b in ab:
c[n - b] += 1
for i in range(n):
c[i + 1] += c[i]
for i, (a, b) in enumerate(ab):
if i + 1 > n - b or a != c[i]:
print("No")
exit(0)
print("Yes")

repovive starter round 10 B - Rise to the Occasion

長さ nn の整数列 aa と正の整数 x,yx, y が与えられます。カウンタ tt は最初 00 です。aa を好きな順に並べ替えてから順に見ていき、値 vv について t≤vt \le v なら tt を xx 増やし、そうでなければ tt を yy 減らします。最後の tt の最大値を求める問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、1≤x,y≤1091 \le x, y \le 10^9、−109≤ai≤109-10^9 \le a_i \le 10^9)。

aa を昇順に並べてシミュレーションした結果が答えです。

kk 個の値を見た時点の tt は、増やした回数を pp として px−(k−p)y=p(x+y)−kypx - (k - p)y = p(x + y) - ky です。よって、同じ個数を見た時点の 2 つのカウンタの値 t≤t′t \le t' の差は x+yx + y の倍数です。

t≤t′t \le t' のとき、同じ値 vv を見たあとも大小は逆転しません。両方が増える場合と両方が減る場合は明らかです。t≤v<t′t \le v < t' で tt だけが増える場合は、t′≥t+(x+y)t' \ge t + (x + y) なので t′−y≥t+xt' - y \ge t + x です(t>v≥t′t > v \ge t' となることはありません)。

したがって、途中のある時点でカウンタが大きいほうが、残りの並びが同じなら最後のカウンタも大きいか等しいです。

並びの中で u>vu > v が u,vu, v の順に隣り合っているとき、v,uv, u の順に入れ替えても、2 つを見たあとのカウンタは小さくならないことを示します。2 つを見る前のカウンタを tt とします。

  • t≤vt \le v のとき:どちらの順でも 1 つ目で増えて t+xt + x になります。2 つ目で増えるのは、元の順では t+x≤vt + x \le v のとき、入れ替えると t+x≤ut + x \le u のときで、後者のほうが条件が弱いです。
  • v<t≤uv < t \le u のとき:元の順では uu で増えて vv で減り、入れ替えると vv で減って uu で増えます(t−y<t≤ut - y < t \le u なので)。どちらも t+x−yt + x - y です。
  • u<tu < t のとき:どちらの順でも 1 つ目で減って t−yt - y になります。2 つ目で増えるのは、元の順では t−y≤vt - y \le v のとき、入れ替えると t−y≤ut - y \le u のときで、後者のほうが条件が弱いです。

どの場合も、入れ替えたほうが増える回数が多いか等しいので、カウンタも大きいか等しいです。上で示したことから、最後のカウンタも小さくなりません。この入れ替えを繰り返すと昇順になるので、昇順が最適です。

計算量はソートの O(nlog⁡n)O(n \log n) です。

Python
n, x, y = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
t = 0
for v in a:
if t > v:
t -= y
else:
t += x
print(t)

repovive starter round 10 A - A Softer Landing

座面の高さが aa と bb の 2 脚の椅子と、厚さが cc と dd の 2 枚のクッションがあります。それぞれの椅子にクッションを 1 枚ずつ置いたとき、2 脚の高さを等しくできるか判定する問題です(1≤a,b,c,d≤1001 \le a, b, c, d \le 100)。

置き方は 2 通りで、高さが等しくなる条件はそれぞれ a+c=b+da + c = b + d と a+d=b+ca + d = b + c です。移項すると a−b=d−ca - b = d - c と a−b=c−da - b = c - d になるので、まとめると ∣a−b∣=∣c−d∣|a - b| = |c - d| です。

Python
a, b, c, d = map(int, input().split())
if abs(a - b) == abs(c - d):
print("Yes")
else:
print("No")

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
    • 外から入る辺のない成分に生存者が必ず残ることを示し、成分ごとに独立に数えて掛け合わせています。

競プロキャンプ2026関西 J - Substring Query

英小文字からなる文字列 SS が与えられます。QQ 個のクエリで文字列 TiT_i が与えられるので、SS と TiT_i の両方の部分文字列である空でない文字列のうち、最長のものの長さを答える問題です(なければ 00)。制約は 1≤∣S∣≤20001 \le |S| \le 2000、1≤Q≤2×1051 \le Q \le 2 \times 10^5、∑∣Ti∣≤106\sum |T_i| \le 10^6 です。

TT の各位置 jj について、TT の jj 文字目で終わる文字列のうち SS の部分文字列であるものの最長の長さを ℓj\ell_j とします。共通の部分文字列はどれも TT のどこかの位置で終わるので、答えは ℓj\ell_j の最大値です。

ℓj\ell_j は、SS の Suffix Automaton を使うと、TT を前から 1 文字ずつ読みながら求められます。Suffix Automaton は SS のすべての部分文字列を受理するオートマトンです。各状態は SS の部分文字列の集まりを表し、状態の数は O(∣S∣)O(|S|) です。

TT の jj 文字目までを読んだとき、長さ ℓj\ell_j の文字列(その位置で終わる、SS の部分文字列である最長の文字列)を表す状態 vv と ℓj\ell_j を持っておきます。次の文字 cc を読むときは、次のようにします。

  • vv から cc で遷移できれば、遷移して長さを 11 増やす。
  • 遷移できなければ、先頭の文字を削って短くする。Suffix Automaton では、これは suffix link をたどることにあたる。遷移できるようになるか初期状態に戻るまでたどってから、遷移を試す。

長さは 1 文字読むごとに高々 11 しか増えないので、suffix link をたどる回数の合計は ∣T∣|T| 以下です。よって、1 つのクエリは O(∣T∣)O(|T|) で処理でき、全体の計算量は O(∣S∣+∑∣Ti∣)O(|S| + \sum |T_i|) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/string/suffix-automaton.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(Q);
STR(S);
SuffixAutomaton sam(S);
rep(Q) {
STR(T);
print(max(sam.match_lengths(T)));
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SuffixAutomaton は Suffix Automaton で、既定では英小文字を扱います。match_lengths(T) は上の ℓj\ell_j を TT の各位置について並べた列を返すので、その最大値を出力しています。

使用ライブラリ:cpp_include@c3d3c0f

競プロキャンプ2026関西 F - Keep Far

NN 個の座席が一列に並んでいて、KK 人が順に 1 人ずつ座ります。各人は、左右の両隣に誰も座っていない空席があればその中から 1 つを選び、なければ空席から好きに 1 つを選んで座ります。最終的に座っている席が文字列 SS の # の位置と一致するような座り方の個数を、998244353998244353 で割った余りで求める問題です(1≤K≤N≤30001 \le K \le N \le 3000、# はちょうど KK 個)。

両隣に誰も座っていない空席を「よい席」と呼びます。座り方は 2 つの段階に分かれます。

  • 前半:よい席がある間は、よい席に座ります。前半に座る席の集合を II とすると、II のどの 2 席も隣り合いません。
  • 後半:よい席がなくなったら、残りの人は好きな空席に座ります。人が増えるとよい席は減る一方なので、後半によい席が復活することはありません。

前半が終わるのは、II に入っていないどの席にも、隣に II の席があるときです。

KK 人とも、座る時点で両隣が空いています。よって、どの順に座ってもルールに従っていて、答えは K!K! です。

隣り合う 2 席のうち後に座る人は、よい席でない席に座るので、後半に座っています。よって、前半は最後まで終わっていなければなりません。つまり II は次の条件を満たします。

  • II は # の席だけからなり、どの 2 席も隣り合わない。
  • II に入っていない席(. の席も含む)はすべて、隣に II の席がある。

特に、どの # とも隣り合わない . があれば、この条件を満たす II はないので答えは 00 です。

逆に、条件を満たす II を 1 つ決めて ∣I∣=i|I| = i とすると、前半の ii 人は II の席に好きな順で座れて i!i! 通り、後半の K−iK - i 人は残りの # の席に好きな順で座れて (K−i)!(K - i)! 通りです。したがって、条件を満たす II のうち ∣I∣=i|I| = i のものの個数を cic_i として、答えは

∑ii! (K−i)! ci\sum_{i} i! \, (K - i)! \, c_i

です。

II の席を左から p1<p2<⋯<pip_1 < p_2 < \dots < p_i とすると、条件は次のように言い換えられます。

  • どの pjp_j も # の席である。
  • pj+1−pjp_{j+1} - p_j は 22 か 33 である(隣り合わず、間の席はどれも II の席と隣り合う)。
  • p1p_1 は 11 か 22、pip_i は N−1N - 1 か NN である(両端の席も II の席と隣り合う)。

そこで、席を左から見ていき、「直前に選んだ席が何個前か」と「これまでに選んだ個数」を状態にして DP をします。計算量は O(N2)O(N^2) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/math/combinatorics.hpp"
#include "shogo-library/math/modint.hpp"
#include "shogo-library/utility/container_func.hpp"
using mint = modint998244353;
using C = Combination<mint>;
void solve() {
LL(N, K);
STR(S);
ll full = true;
rep(i, N) {
if (S[i] == '#')
continue;
if (i > 0 && S[i - 1] == '#')
continue;
if (i < N - 1 && S[i + 1] == '#')
continue;
full = false;
}
rep(i, 1, N) {
if (S[i - 1] == '#' && S[i] == '#' && !full) {
print(0);
return;
}
}
if (not full) {
print(C::factorial(K));
return;
}
ary<vec<mint>, 3> dp = {vec<mint>(N + 1), vec<mint>(N + 1), vec<mint>(N + 1)};
dp[1][0] = 1;
for (char c : S) {
vec<mint> ndp(N + 1);
if (c == '#') {
rep(i, 1, N + 1) {
ndp[i] += dp[0][i - 1];
ndp[i] += dp[1][i - 1];
}
}
std::swap(dp[0], dp[1]);
std::swap(dp[1], dp[2]);
std::swap(dp[2], ndp);
}
mint ans = 0;
rep(i, K + 1) {
ans += C::factorial(K - i) * C::factorial(i) * (dp[1][i] + dp[2][i]);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

full は「どの . の席も # の席と隣り合う」かどうかです。full でないときは、隣り合う # があれば 00、なければ K!K! を出力します。full のときは、隣り合う # がなくても DP に進みますが、そのときは II がすべての # の席になるしかないので、DP でも K!K! が求まります。

DP では、今の席を見る直前の時点で、dp[2][i] が「直前の席を選んだ」、dp[1][i] が「2 つ前の席を選んだ」、dp[0][i] が「3 つ前の席を選んだ」状態で、ii 個選んだときの場合の数です。今の席が # なら、dp[0] と dp[1] から今の席を選べます。そのあと 3 つの配列をずらして、次の席から見た状態にしています。はじめに dp[1][0] = 1 としているのは、席 11 の 2 つ左に仮の席が選ばれているとみなすためで、こうすると最初に選ぶ席は 11 か 22 になります。最後は、最後に選んだ席が NN か N−1N - 1 である dp[2] と dp[1] を使います。

modint998244353 は 998244353998244353 で割った余りで計算する整数型で、C::factorial(n) は n!n! を返します。場合の数は非常に大きくなるので、DP の配列も mint にしておく必要があります。

使用ライブラリ:cpp_include@9c33ee7

競プロキャンプ2026関西 E - Join Wars

NN 人のプレイヤーと MM 個のインスタンスがあり、インスタンス ii の定員は AiA_i です。満員のインスタンスに入ろうとしたプレイヤーは、そのインスタンスの待機列の最後尾に並びます。次の 2 種類のクエリを合わせて QQ 個処理する問題です(1≤N,M,Q≤5×1051 \le N, M, Q \le 5 \times 10^5)。

  • 1 x y:プレイヤー xx が今の居場所を離れ、インスタンス yy に入ろうとする。インスタンスから退出した場合は、そのインスタンスの待機列の先頭のプレイヤーが入場する。待機列に並んでいた場合は、列から外れる。
  • 2 z:プレイヤー zz がインスタンス pp に入場していれば 1 p、インスタンス pp の待機列に並んでいれば 2 p、どちらでもなければ -1 を出力する。

インスタンスごとに、入場しているプレイヤーの集合と、待機列を管理して、書かれているとおりにシミュレーションします。

待機列では、先頭(最も早く並んだプレイヤー)を取り出す操作のほかに、途中のプレイヤーが抜ける操作があります。そのため、通常のキューではなく、(並んだ時刻, プレイヤー) の組を入れた順序付き集合(C++ の std::set)で管理します。集合の最小の要素が待機列の先頭です。

クエリ 1 では、まずプレイヤー xx を今いる場所から取り除きます。インスタンスから退出した場合は、空いた枠に待機列の先頭を入場させます。続けて、xx をインスタンス yy の待機列の最後尾に入れてから、定員に空きがある間は待機列の先頭を入場させます。yy に空きがあれば、待機列は空のはずなので、xx がそのまま入場することになります。

各プレイヤーについて、今いるインスタンスの番号と、並んだ時刻を記録しておきます。こうすると、集合から取り除くときの要素も、クエリ 2 で待機列にいるかどうかも、O(log⁡N)O(\log N) で分かります。全体の計算量は O(M+Qlog⁡N)O(M + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M, Q);
VL(A, M);
vec<set<pl>> room(M), que(M);
vl idx(N, -1);
vl tm(N, -1);
rep(i, Q) {
LL(q);
if (q == 1) {
LL(x, y);
x--, y--;
ll &z = idx[x];
if (z >= 0) {
if (room[z].contains({tm[x], x})) {
room[z].erase({tm[x], x});
while (len(room[z]) < A[z] && len(que[z])) {
room[z].insert(que[z].extract(min(que[z])));
}
} else {
que[z].erase({tm[x], x});
}
}
tm[x] = i;
z = y;
que[z].insert({i, x});
while (len(room[z]) < A[z] && len(que[z])) {
room[z].insert(que[z].extract(min(que[z])));
}
} else {
LL(z);
z--;
if (idx[z] >= 0) {
print(1 + que[idx[z]].contains({tm[z], z}), idx[z] + 1);
} else {
print(-1);
}
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

room[z] がインスタンス z に入場しているプレイヤーの集合、que[z] が待機列です。どちらも要素は (インスタンス z に入ろうとしたクエリの番号, プレイヤー) の組です。idx[x] はプレイヤー x がいるインスタンス(どこにもいなければ −1-1)、tm[x] は最後にクエリ 1 で動いたときのクエリの番号です。z は idx[x] への参照なので、z = y で idx[x] が更新されます。

min(que[z]) は待機列の先頭の要素で、extract で que[z] から取り出し、そのまま room[z] に入れています。クエリ 2 では、que[idx[z]] に入っていれば待機列、そうでなければ入場中です。

使用ライブラリ:cpp_include@9c33ee7

競プロキャンプ2026関西 D - Flowers

H×WH \times W のマス目に、十字形(中心とその上下左右の 5 マス)の「花」が、はみ出さず重ならないようにいくつか描かれています。描かれたマスが # で与えられるので、すべての花の中心を求める問題です(3≤H,W≤10003 \le H, W \le 1000)。

マス目を上の行から順に、各行は左から順に見ていきます。最初に見つかった # は、ある花の一番上のマスです。花の 5 マスのうち、一番上のマスだけがほかの 4 マスより上の行にあり、見る順番が最も早いからです。

そこで、# が見つかったら、その 1 つ下を中心とする花を答えに加え、その花の 5 マスを . に戻します。こうすると、次に見つかる # も、残っている花のどれかの一番上のマスになります。残っている花のマスより前にあるマスは、すべて見終わっていて、そこにあった花は消してあるからです。

最後まで見れば、すべての花の中心が求まります。計算量は O(HW)O(HW) です。

Python
from itertools import product
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
ans = []
for i, j in product(range(H), range(W)):
if S[i][j] == "#":
ans.append((i + 2, j + 1))
S[i][j] = "."
S[i + 1][j - 1] = "."
S[i + 1][j] = "."
S[i + 1][j + 1] = "."
S[i + 2][j] = "."
print(len(ans))
for x, y in ans:
print(x, y)

product(range(H), range(W)) は、上の行から順に、各行は左から順に (i, j) を並べます。コードの座標は 0 始まりなので、中心 (i+1,j)(i + 1, j) を 1 始まりに直した (i + 2, j + 1) を答えに加えています。花ははみ出さないように描かれているので、S[i + 2][j] などの添字が範囲外になることはありません。

競プロキャンプ2026関西 C - Comfortable Roads

NN 個の町があり、はじめは道がありません。2 つの町を結ぶ道を追加して、どの町 ii からもすべての町へ DiD_i 本以下の道で行けるようにします。追加する道の本数の最小値を求める問題です(2≤N≤3×1052 \le N \le 3 \times 10^5、1≤Di≤N−11 \le D_i \le N - 1)。

Di=1D_i = 1 の町の個数を kk とします。

すべての町がつながっている必要があるので、道は N−1N - 1 本以上必要です。1 つの町を中心にして、残りの N−1N - 1 個の町とそれぞれ結ぶと、中心からはどの町へも 11 本で、ほかの町からはどの町へも 22 本以下で行けます。k=0k = 0 なのですべての ii で Di≥2D_i \ge 2 となり、条件を満たします。よって答えは N−1N - 1 です。

Di=1D_i = 1 の町 ii は、ほかのすべての町と直接結ばれていなければなりません。よって、Di=1D_i = 1 の町のどれかを端点に持つ道は、すべて必要です。その本数は、Di=1D_i = 1 の町と別の町の組の個数で、

(N−1)+(N−2)+⋯+(N−k)(N - 1) + (N - 2) + \dots + (N - k)

です。Di=1D_i = 1 の町を 1 つずつ見て、まだ数えていない町との組を足していくとこの式になります。

逆に、この道だけで条件を満たします。Di=1D_i = 1 の町はすべての町と直接結ばれています。それ以外の町は、Di=1D_i = 1 の町を経由してどの町へも 22 本以下で行けて、Di≥2D_i \ge 2 です。よって、これが答えです。

計算量は O(N)O(N) です。

Python
N = int(input())
D = list(map(int, input().split()))
ans = 0
k = 0
for d in D:
if d == 1:
k += 1
ans += N - k
if ans == 0:
ans += N - 1
print(ans)

Di=1D_i = 1 の町が見つかるたびに、それが何個目かを k として、N−kN - k を足しています。k≥1k \ge 1 なら ans は N−1N - 1 以上になるので、ans == 0 となるのは k=0k = 0 のときだけです。

競プロキャンプ2026関西 B - Evaluate F and G

e は空文字列、f(X) は文字列 XX の先頭に f をつけたもの、g(X) は先頭に g をつけたもの、X+Y は XX と YY の連結を表します。これらを組み合わせた式 SS が与えられるので、評価した文字列を求める問題です(1≤∣S∣≤2×1051 \le |S| \le 2 \times 10^5)。

式の値は、SS に現れる文字 f と g を、現れる順に並べた文字列です。

式の組み立て方に沿って確かめます。

  • e は空文字列で、f も g も含みません。
  • f(X) の値は f に XX の値を続けたものです。式の中でも f は XX の前にあります。g(X) も同じです。
  • X+Y の値は XX の値に YY の値を続けたものです。式の中でも XX は YY の前にあります。

したがって、SS から f と g だけを取り出せば答えになります。

Python
print("".join(c for c in input() if c in "fg"))

f と g 以外の文字(e、(、)、+)を取り除いています。答えが空文字列のときは、改行だけが出力されます。

競プロキャンプ2026関西 A - km - n = k

整数 XX が与えられます。1≤k,m,n≤X1 \le k, m, n \le X を満たす整数の組 (k,m,n)(k, m, n) のうち、km−n=kkm - n = k を満たすものの個数を求める問題です(2≤X≤1062 \le X \le 10^6)。

km−n=kkm - n = k は n=k(m−1)n = k(m - 1) と変形できます。nn は kk と mm から決まるので、nn が 11 以上 XX 以下になるような (k,m)(k, m) の組を数えればよいです。

t=m−1t = m - 1 とおくと、条件は 1≤t≤X−11 \le t \le X - 1 かつ kt≤Xkt \le X です(kt≥1kt \ge 1 は t≥1t \ge 1 から成り立ちます)。kk を固定すると、条件を満たす tt は 11 以上 min⁡(⌊X/k⌋,X−1)\min(\lfloor X / k \rfloor, X - 1) 以下のすべての整数です。これを k=1,…,Xk = 1, \dots, X について足し合わせれば答えです。

⌊X/k⌋\lfloor X / k \rfloor は割り算で直接求められますが、下のコードでは「kt≤Xkt \le X を満たす最大の tt」を二分探索で求めています。計算量は O(Xlog⁡X)O(X \log X) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/binary-search.hpp"
void solve() {
LL(X);
ll ans = 0;
rep(k, 1, X + 1) {
ans += binary_search(1, X, [=](ll mm) { return k * mm <= X; });
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

mm が上の t=m−1t = m - 1 です。binary_search(ok, ng, f) は、f(ok) が真、f(ng) が偽であるとして、f が真になる側の境界の値を返します。ng を XX にしているので、返り値は XX 未満で kt≤Xkt \le X を満たす最大の tt、つまり min⁡(⌊X/k⌋,X−1)\min(\lfloor X / k \rfloor, X - 1) です。k≤Xk \le X なので、f(1) は常に真です。

使用ライブラリ:cpp_include@9c33ee7

DOJ Beginner Contest 12 E - Shirogane Wants to Sing

長さ NN の非負整数列 AA が与えられます。次の条件をすべて満たす長さ NN の非負整数列 BB の個数を 109+710^9 + 7 で割った余りを求める問題です。

  • B1=0B_1 = 0。
  • すべての 1≤i<N1 \le i < N について ∣Bi−Bi+1∣≤K|B_i - B_{i+1}| \le K。
  • ∑i=1N∣Ai−Bi∣≤E\sum_{i=1}^{N} |A_i - B_i| \le E。

制約は 2≤N≤1002 \le N \le 100、0≤K≤200 \le K \le 20、0≤E≤500 \le E \le 50、0≤Ai≤500 \le A_i \le 50 です。

BB を前から 1 つずつ決めていく DP をします。次の値を決めるのに必要なのは、直前の値 BiB_i と、それまでの誤差の合計だけです。そこで

dpi[e][b]=(B1,…,Bi のうち、誤差の合計が e で Bi=b であるものの個数)\mathrm{dp}_i[e][b] = (B_1, \dots, B_i \text{ のうち、誤差の合計が } e \text{ で } B_i = b \text{ であるものの個数})

とします。dp1\mathrm{dp}_1 は dp1[A1][0]=1\mathrm{dp}_1[A_1][0] = 1 だけが 11 です(A1>EA_1 > E なら答えは 00 です)。dpi[e][b]\mathrm{dp}_i[e][b] から、∣b−b′∣≤K|b - b'| \le K を満たす各 b′b' について、e′=e+∣Ai+1−b′∣≤Ee' = e + |A_{i+1} - b'| \le E なら dpi+1[e′][b′]\mathrm{dp}_{i+1}[e'][b'] に足します。答えは dpN\mathrm{dp}_N の値の総和です。

BiB_i のとりうる範囲は有限です。∣Ai−Bi∣≤E|A_i - B_i| \le E なので、Bi≤Ai+E≤max⁡A+EB_i \le A_i + E \le \max A + E です。よって bb は 00 以上 M=max⁡A+E≤100M = \max A + E \le 100 以下だけを考えれば十分です。

計算量は O(NEMK)O(NEMK) で、最大でも 100×51×101×41≈2×107100 \times 51 \times 101 \times 41 \approx 2 \times 10^7 回程度です。

Python
MOD = 10**9 + 7
N, K, E = map(int, input().split())
A = list(map(int, input().split()))
if A[0] > E:
print(0)
exit(0)
M = max(A) + E
dp = [[0 for i in range(M + 1)] for j in range(E + 1)]
dp[A[0]][0] = 1
for a in A[1:]:
ndp = [[0 for i in range(M + 1)] for j in range(E + 1)]
for i in range(E + 1):
for j in range(M + 1):
for k in range(j - K, j + K + 1):
if k not in range(M + 1):
continue
if abs(a - k) + i > E:
continue
ndp[abs(a - k) + i][k] += dp[i][j]
ndp[abs(a - k) + i][k] %= MOD
dp = ndp
print(sum(sum(a) % MOD for a in dp) % MOD)

dp[i][j] が、誤差の合計が i で直前の値が j である数列の個数です。k が次の値 Bi+1B_{i+1} の候補で、範囲 [0,M][0, M] から外れるものと、誤差の合計が EE を超えるものを飛ばしています。

DOJ Beginner Contest 12 F - Half Shuffle

長さ 2N2N の順列 PP が与えられます。1 回の操作では、相異なる位置をちょうど NN 個選び、そこにある値を好きな順に並べ替えます。PP を昇順に並べるのに必要な操作回数の最小値を求める問題です(2≤N≤30002 \le N \le 3000、全テストケースの NN の総和は 30003000 以下)。

PP を巡回置換に分解し、長さが 22 以上のサイクルの長さを l1,…,lkl_1, \dots, l_k とします。正しい位置にない値の個数は s=l1+⋯+lks = l_1 + \dots + l_k です。答えは次のとおりです。

  • s=0s = 0 なら 00 回。
  • 1≤s≤N1 \le s \le N なら 11 回。
  • s>Ns > N で、「s<2Ns < 2N」または「いくつかのサイクルの長さの和をちょうど NN にできる」なら 22 回。
  • それ以外(s=2Ns = 2N で、和を NN にできない)なら 33 回。

1 回の操作で動かせるのは NN 個なので、1 回で済むのは s≤Ns \le N のときだけです。このときは、正しい位置にない位置をすべて選び、足りない分は正しい位置にある位置で埋めて、そのまま並べ直せば終わります。

s>Ns > N なら 2 回以上かかります。

いくつかのサイクルの長さの和がちょうど NN なら、1 回目にそれらのサイクルの位置を選んで正しく並べます。残りは s−N≤Ns - N \le N 個なので、2 回目で終わります。

s<2Ns < 2N のときも 2 回でできます。サイクルの一部を 1 回の操作で直す方法を考えます。サイクル x→Px→PPx→⋯x \to P_x \to P_{P_x} \to \cdots から、つながった rr 個の位置を選びます。そこに並ぶ値のうち r−1r - 1 個は、正しい位置が選んだ位置の中にあります。よって、この操作で r−1r - 1 個を正しい位置に置けて、サイクルの長さは r−1r - 1 だけ短くなります。1 回目では、サイクルを丸ごと選べるだけ選び、残りの rr 個の枠は次のサイクルの一部で埋めます。すると、正しい位置に置ける値は N−1N - 1 個以上になります。残りは s−(N−1)≤Ns - (N - 1) \le N 個なので、2 回目で終わります。

逆に s=2Ns = 2N のときに 2 回でできたとします。1 回目に選ばなかった NN 個の位置は、1 回目のあとも正しくないままです。2 回目で動かせるのは NN 個なので、1 回目に選んだ NN 個の位置は、1 回目ですべて正しくならなければいけません。そのためには、選んだ位置にある値の正しい位置が、すべて選んだ位置の中になければなりません。これは、選んだ位置がいくつかのサイクルの和集合であることを意味します。つまり、サイクルの長さの和をちょうど NN にできなければ、2 回ではできません。

上の「サイクルの一部を直す」方法で 1 回操作すると、残りは s−(N−1)≤N+1<2Ns - (N - 1) \le N + 1 < 2N 個になります(N≥2N \ge 2 です)。ここから 2 回で終わるので、どの場合も 3 回あれば十分です。

サイクルの長さの和を NN にできるか

Section titled “サイクルの長さの和を NNN にできるか”

部分和問題の DP で判定します。dp[j]\mathrm{dp}[j] を「いくつかのサイクルを選んで長さの和を jj にできるか」として、サイクルを 1 つずつ加えて更新します。サイクルは高々 NN 個なので、計算量は O(N2)O(N^2) です。

Python
for _ in range(int(input())):
N = int(input())
P = list(map(lambda x: int(x) - 1, input().split()))
visited = [False] * (2 * N)
l = []
for i in range(2 * N):
if visited[i]:
continue
x = i
visited[x] = True
r = [x]
while i != P[x]:
x = P[x]
visited[x] = True
r.append(x)
if len(r) > 1:
l.append(len(r))
s = sum(l)
dp = [0] * (N + 1)
dp[0] = 1
for x in l:
for i in reversed(range(x, N + 1)):
dp[i] |= dp[i - x]
if s == 0:
print(0)
elif s <= N:
print(1)
elif dp[N] or s < 2 * N:
print(2)
else:
print(3)

前半では、まだ見ていない位置 i から P をたどってサイクルを取り出し、長さが 22 以上ならその長さを l に入れています。後半の dp は部分和問題の DP で、i を大きいほうから回すことで、同じサイクルを 2 回使わないようにしています。

DOJ Beginner Contest 12 D - Yet Another Hamiltonian Path Problem

頂点 1,…,N1, \dots, N の有向グラフがあり、各頂点 ii に Ai∈{0,1}A_i \in \{0, 1\} が与えられます。Ai=0A_i = 0 なら、すべての j<ij < i に対して辺 i→ji \to j があります。Ai=1A_i = 1 なら、すべての j>ij > i に対して辺 i→ji \to j があります。すべての頂点をちょうど 1 回ずつ通る経路(ハミルトン路)を 1 つ出力する問題です。存在しなければ −1-1 を出力します(2≤N≤5×1052 \le N \le 5 \times 10^5、全テストケースの NN の総和は 5×1055 \times 10^5 以下)。

Ai=0A_i = 0 の頂点を「左向き」、Ai=1A_i = 1 の頂点を「右向き」と呼びます。左向きの頂点どうしは番号の大きい順にたどれて、右向きの頂点どうしは番号の小さい順にたどれます。あとは、2 つの列をつなげられるかどうかです。

  • AN=0A_N = 0 のとき:右向きの頂点を小さい順にたどり、続けて左向きの頂点を大きい順にたどります。つなぎ目では、最後の右向きの頂点から左向きの頂点 NN に進みます。NN はどの頂点より番号が大きいので、この辺はあります。
  • A1=1A_1 = 1 のとき:左向きの頂点を大きい順にたどり、続けて右向きの頂点を小さい順にたどります。つなぎ目では、最後の左向きの頂点から右向きの頂点 11 に進みます。11 はどの頂点より番号が小さいので、この辺はあります。
  • A1=0A_1 = 0 かつ AN=1A_N = 1 のとき:頂点 11 は左向きなのに自分より小さい頂点がなく、頂点 NN は右向きなのに自分より大きい頂点がありません。どちらも出る辺がないので、経路の終点にしか置けません。終点は 1 つなので、ハミルトン路は存在しません。

計算量は O(N)O(N) です。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
if A[0] == 0 and A[-1] == 1:
print(-1)
continue
ans = []
if A[-1] == 0:
for i in range(N):
if A[i] == 1:
ans.append(i + 1)
for i in reversed(range(N)):
if A[i] == 0:
ans.append(i + 1)
else:
assert A[0] == 1
for i in reversed(range(N)):
if A[i] == 0:
ans.append(i + 1)
for i in range(N):
if A[i] == 1:
ans.append(i + 1)
print(*ans)

A は 0 始まりなので、頂点の番号は i + 1 です。最初の if で −1-1 の場合を除いているので、else に来たときは A1=1A_1 = 1 です。

DOJ Beginner Contest 12 C - Nature-Friendly Village

R×CR \times C のグリッドの各マスは、家(#)か空き地(.)です。空き地に 1 本ずつ木を植えます。家ごとに周囲 8 マスに植えた木の本数を数え、その総和を KK 以上にしたいです。植える木の本数の最小値を求める問題です。できなければ −1-1 を出力します(0≤K≤8RC0 \le K \le 8RC、全テストケースの RCRC の総和は 10610^6 以下)。

総和を、木の側から数え直します。空き地 xx の周囲 8 マスにある家の個数を cxc_x とすると、xx に植えた木は、総和をちょうど cxc_x だけ増やします。したがって総和は、木を植えた空き地の cxc_x の和です。

この和を KK 以上にするには、cxc_x の大きい空き地から順に植えていくのが最善です。何本植えるにしても、同じ本数なら cxc_x の大きいほうから選んだときに和が最大になるからです。すべての空き地に植えても KK に届かなければ、答えは −1-1 です。

計算量はソートがいちばん重く、O(RClog⁡(RC))O(RC \log(RC)) です。

Python
from itertools import product
for _ in range(int(input())):
R, C, K = map(int, input().split())
S = [input() for i in range(R)]
l = []
for i, j in product(range(R), range(C)):
if S[i][j] == "#":
continue
c = 0
for di, dj in product(range(-1, 2), repeat=2):
if di == dj == 0:
continue
ni, nj = i + di, j + dj
if ni not in range(R):
continue
if nj not in range(C):
continue
if S[ni][nj] == "#":
c += 1
l.append(c)
l.sort()
s = 0
ans = 0
while l and s < K:
s += l.pop()
ans += 1
if s < K:
print(-1)
else:
print(ans)

l は空き地ごとの cxc_x の列です。昇順にソートして末尾から pop することで、大きいほうから取り出しています。s が KK に届くか、空き地がなくなるまで植えます。K=0K = 0 のときは 1 本も植えずに 00 を出力します。

DOJ Beginner Contest 12 B - New City Planning

NN 棟の建物を建てます。建物 ii の高さは 11 以上 AiA_i 以下の整数にでき、高さが hh の建物 1 棟につき、都市の完成度が BhB_h 増えます。完成度の合計の最大値を求める問題です(1≤Ai,Bh≤1051 \le A_i, B_h \le 10^5、M=max⁡AiM = \max A_i として、全テストケースの N+MN + M の総和は 2×1052 \times 10^5 以下)。

建物どうしは影響し合わないので、建物ごとに完成度の増え方が最大になる高さを選べばよいです。建物 ii で得られる最大値は max⁡(B1,…,BAi)\max(B_1, \dots, B_{A_i}) です。

BB の先頭からの最大値(累積 max)Ch=max⁡(B1,…,Bh)C_h = \max(B_1, \dots, B_h) を前計算しておけば、答えは CA1+⋯+CANC_{A_1} + \dots + C_{A_N} です。計算量は O(N+M)O(N + M) です。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
for i in range(1, len(B)):
B[i] = max(B[i], B[i - 1])
print(sum(B[a - 1] for a in A))

B をその場で累積 max に書き換えています。リストは 0 始まりなので、CAiC_{A_i} は B[a - 1] です。

DOJ Beginner Contest 12 A - BCD Participation

BCD に参加するには、DOJ のレーティングが 00 以上 22002200 以下でなければなりません。レーティングが NN のとき、BCD に参加できるかを判定する問題です。テストケースは TT 個あります(1≤T≤100001 \le T \le 10000、0≤N≤40000 \le N \le 4000)。

0≤N≤22000 \le N \le 2200 なら YES、そうでなければ NO を出力します。

Python
for _ in range(int(input())):
if 0 <= int(input()) <= 2200:
print("YES")
else:
print("NO")

ABC480 F - Cake Cutting

大きさ A1,…,ANA_1, \dots, A_N の NN 個のケーキを MM 人に配ります。大きさの総和を SS とし、SS は MM の倍数です。ケーキを 1 つ選んで自由に 2 つに切り分ける操作を何回か行ったあと、全員がもらう大きさの合計がちょうど S/MS / M になるように配りたいです。操作回数の最小値を求める問題です(1≤N≤201 \le N \le 20、1≤M≤1001 \le M \le 100、1≤Ai≤1091 \le A_i \le 10^9)。

t=S/Mt = S / M とします。

ケーキを cc 個のグループに分けて、どのグループも大きさの和が tt の倍数になるようにできたとします。このとき、操作回数 M−cM - c で配れます。グループを順に一列に並べて、先頭から長さ tt ずつ切っていけばよいからです。M−1M - 1 か所の切れ目のうち、グループの境目にある c−1c - 1 か所はケーキを切らずに済むので、切る回数は高々 (M−1)−(c−1)=M−c(M - 1) - (c - 1) = M - c です。

逆に、どんな配り方でも操作回数は M−cM - c 以上です。ケーキと人を頂点とし、人がケーキの一部をもらっているときにその 2 つを辺で結んだグラフを考えます。各辺は 1 つ以上の切れ端に対応するので、切れ端の個数は辺の本数 EE 以上です。1 回の操作で切れ端は 1 個増えるので、操作回数は E−NE - N 以上です。グラフの連結成分の個数を cc とすると、頂点は N+MN + M 個なので E≥N+M−cE \ge N + M - c で、操作回数は M−cM - c 以上になります。各連結成分のケーキの大きさの和は、そこに含まれる人数の tt 倍です。また、どの人もケーキをもらうので、どの連結成分にもケーキが含まれます。よって、連結成分ごとにケーキを分ければ、和が tt の倍数になる cc 個のグループができます。

したがって答えは、「ケーキを、大きさの和がどれも tt の倍数になるようにグループ分けするときのグループの個数の最大値」を cc として、M−cM - c です。

ケーキを一列に並べて、先頭からの和が tt の倍数になる位置で区切ると考えれば、グループ分けは並べ方と対応します。グループの個数は、先頭からの和が tt の倍数になる位置の個数(最後のケーキの後ろも含む)です。

そこで、ケーキの集合 UU に対して、dp[U]\mathrm{dp}[U] を「UU のケーキを先頭に並べるとき、UU の中で先頭からの和が tt の倍数になる位置の個数の最大値」とします。UU の最後に置くケーキ ii で場合分けすると、

dp[U]=max⁡i∈U(dp[U∖{i}]+[∑j∈UAj≡0(modt)])\mathrm{dp}[U] = \max_{i \in U} \left( \mathrm{dp}[U \setminus \{i\}] + [\textstyle\sum_{j \in U} A_j \equiv 0 \pmod t] \right)

です。[⋯ ][\cdots] は条件が成り立てば 11、成り立たなければ 00 を表します。答えは M−dp[{1,…,N}]M - \mathrm{dp}[\{1, \dots, N\}] です。

計算量は O(2NN)O(2^N N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/bit.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M);
VL(A, N);
ll t = sum(A) / M;
val<2> dp(1 << N, al<2>{-1, 0});
dp[0] = {0, 0};
rep(u, 1, 1 << N) {
for (auto [i, v] : remove_one(u)) {
ll y = (dp[v][1] + A[i]) % t;
chmax(dp[u], al<2>{dp[v][0] + (y == 0), y});
}
}
print(M - dp.back()[0]);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

dp[u] は 2 つの値の組で、dp[u][0] が上の dp[U]\mathrm{dp}[U]、dp[u][1] が UU のケーキの大きさの和を tt で割った余りです。余りは UU だけで決まるので、組を辞書順で chmax しても、dp[u][0] の最大値がとられます。remove_one(u) は、u に含まれる位置 i と、u から i を除いた集合 v の組を列挙します。

使用ライブラリ:cpp_include@9c33ee7

ABC480 E - Product-Bounded Arithmetic Sequences

長さが 33 以上で、公差が正の、正整数からなる等差数列を良い数列と呼びます。良い数列のうち、要素の総積が NN 以下であるものの個数を求める問題です(1≤N≤10181 \le N \le 10^{18})。

良い数列は、長さ ll、初項 aa、公差 dd で決まります(l≥3l \ge 3、a≥1a \ge 1、d≥1d \ge 1)。総積は

a(a+d)(a+2d)⋯(a+(l−1)d)a (a + d) (a + 2d) \cdots (a + (l - 1)d)

です。答えは 101210^{12} 程度になる(入力例 2)ので 1 つずつ数えることはできませんが、ll と aa を全探索して、dd の個数をまとめて数えれば間に合います。

  • ll の範囲:総積が最小になるのは a=d=1a = d = 1 のときで、その値は l!l! です。20!≈2.4×1018>101820! \approx 2.4 \times 10^{18} > 10^{18} なので、l≤19l \le 19 です。
  • aa の範囲:総積は a3a^3 より大きいので、a<106a < 10^6 です。
  • dd の個数:ll と aa を決めると、総積は dd について単調増加です。よって総積が NN 以下になる dd は 11 以上のある値 DD 以下のすべての整数で、その個数 DD は二分探索で求められます。総積は 2d22d^2 より大きいので、D<109D < 10^9 です。

aa を大きくしても総積は増えるので、ある aa で D=0D = 0 になったら、それより大きい aa も調べる必要はありません。計算量は、l=3l = 3 のときの 10610^6 個の aa のそれぞれで二分探索をするのがいちばん重く、全体で 10810^8 回程度の計算です。

C++
#include "shogo-library/base/all"
#include "shogo-library/math/saturating.hpp"
#include "shogo-library/utility/binary-search.hpp"
void solve() {
LL(N);
ll ans = 0;
rep(l, 3, 20) {
rep(a, 1, 1e6) {
ll ng = 1e9;
ll ok = binary_search(0, ng, [=](ll x) {
ll p = a, t = a;
rep(l - 1) {
t += x;
p = saturating_mul(p, t);
if (p > N)
break;
}
return p <= N;
});
if (ok == 0)
break;
ans += ok;
}
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

binary_search(ok, ng, f) は、f(ok) が真、f(ng) が偽であるとして、f が真になる側の境界の値を返します。ここでは f(x) が「公差 x のときの総積が NN 以下か」なので、返り値がそのまま DD になります。f(0) が偽(つまり al>Na^l > N)のときも、すべての x で偽なので 00 が返り、D=0D = 0 として扱えます。

総積の計算では、saturating_mul で掛け算がオーバーフローしたときに long long の最大値に丸めています。

使用ライブラリ:cpp_include@9c33ee7

ABC480 D - Concatenation of Prefixes

長さ NN の整数列 AA が与えられます。i=1,2,…,Ni = 1, 2, \dots, N の順に (A1,…,Ai)(A_1, \dots, A_i) を末尾に連結して、長さ N(N+1)2\frac{N(N+1)}{2} の数列 BB を作ります。QQ 個の質問 (L,R)(L, R) について、BL+⋯+BRB_L + \dots + B_R を求める問題です(1≤N,Q≤1051 \le N, Q \le 10^5、−108≤Ai≤108-10^8 \le A_i \le 10^8)。

BB の先頭からの和 f(x)=B1+⋯+Bxf(x) = B_1 + \dots + B_x が求められれば、答えは f(R)−f(L−1)f(R) - f(L - 1) です。

BB は、kk 番目のかたまりが (A1,…,Ak)(A_1, \dots, A_k) であるようなかたまりの連結です。kk 番目のかたまりの長さは kk なので、はじめの ii 個のかたまりの長さの合計は Ti=i(i+1)2T_i = \frac{i(i+1)}{2} です。また、AA の累積和を Pj=A1+⋯+AjP_j = A_1 + \dots + A_j とすると、kk 番目のかたまりの和は PkP_k です。

f(x)f(x) を求めるには、まず Ti≤xT_i \le x となる最大の ii を求めます。B1,…,BxB_1, \dots, B_x は、はじめの ii 個のかたまりと、i+1i + 1 番目のかたまりの先頭 x−Tix - T_i 個からなります。したがって

f(x)=(P1+⋯+Pi)+Px−Tif(x) = (P_1 + \dots + P_i) + P_{x - T_i}

です。PP と、PP の累積和を前計算しておけば、f(x)f(x) は ii を求めるだけで計算できます。TiT_i は増加列なので、ii は二分探索で求められます。

計算量は O(N+Qlog⁡N)O(N + Q \log N) です。∣f(x)∣|f(x)| は最大で N(N+1)2×108≈5×1017\frac{N(N+1)}{2} \times 10^8 \approx 5 \times 10^{17} 程度なので、64 ビット整数に収まります。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/binary-search.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, Q);
VL(A, N);
vl tmp = {0};
vl s0 = {0}, s1 = {0};
rep(i, N) {
s0.push_back(s0.back() + A[i]);
s1.push_back(s1.back() + s0.back());
tmp.push_back(tmp.back() + i + 1);
}
auto q = [&](ll x) {
ll i = bisect_right(tmp, x) - 1;
return s1[i] + s0[x - tmp[i]];
};
rep(Q) {
LL(L, R);
print(q(R) - q(L - 1));
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

tmp[i] が TiT_i、s0[j] が PjP_j、s1[i] が P1+⋯+PiP_1 + \dots + P_i です。bisect_right(tmp, x) は tmp の中で x より大きい最初の要素の位置(Python の bisect.bisect_right と同じ)を返すので、そこから 11 を引くと Ti≤xT_i \le x となる最大の ii になります。q(x) が f(x)f(x) です。

使用ライブラリ:cpp_include@9c33ee7

ABC480 C - Self-Stopping Shower

シャワーのボタンを時刻 tt に押すと、時刻 tt から t+Kt + K までお湯が出ます(お湯が出ている間に押した場合も、最後に押した時刻から KK 秒間出ます)。NN 人の青木君が、それぞれ時刻 AiA_i にボタンを押します。時刻 00 から TT までずっとお湯が出ているようにするために、高橋君がボタンを押す回数の最小値を求める問題です(1≤N≤2×1051 \le N \le 2 \times 10^5、1≤K,T≤1091 \le K, T \le 10^9、0≤Ai≤1090 \le A_i \le 10^9)。

お湯が出ている時刻は、誰かがボタンを押した時刻 tt についての区間 [t,t+K][t, t + K] の和集合です。したがってこの問題は、青木君の区間 [Ai,Ai+K][A_i, A_i + K] に長さ KK の区間をいくつか足して、[0,T][0, T] を覆うときの、足す区間の個数の最小値を求める問題になります。

青木君の区間だけでは覆われない部分は、いくつかのすき間に分かれます。すき間の長さが gg なら、長さ KK の区間は少なくとも ⌈g/K⌉\lceil g / K \rceil 個必要で、すき間の左端から KK ずつずらして置けばちょうどその個数で覆えます。また、1 つの区間が 2 つのすき間にまたがることはありません。2 つのすき間の間には青木君の区間が丸ごと入っていて、またぐには長さが KK より大きくなければならないからです。よって、すき間ごとの ⌈g/K⌉\lceil g / K \rceil の和が答えです。

すき間は、青木君の押す時刻を小さい順に見ていけば求められます。今までの区間で覆われている右端を pp とします(はじめは p=0p = 0 です)。次の時刻 bb が p<bp < b なら、pp から bb までの長さ b−pb - p のすき間があります。最後に、TT を時刻の列に加えておくと、TT までに残ったすき間も同じように扱えます。TT 以上の時刻に押される分は [0,T][0, T] を覆うのに関係ないので、取り除いておきます。

計算量はソートがいちばん重く、O(Nlog⁡N)O(N \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, K, T);
VL(A, N);
vl B = {T};
for (ll a : A)
if (a < T)
B.push_back(a);
sort(B);
ll ans = 0, p = 0;
for (ll b : B) {
if (p < b)
ans += ceildiv(b - p, K);
chmax(p, b + K);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

B は、TT と、TT より前の青木君の時刻を並べてソートした列です。p が今まで覆えている右端で、b の前にすき間があれば ceildiv(b - p, K)(⌈(b−p)/K⌉\lceil (b - p) / K \rceil)回押します。そのあと b に押された分で、右端は b + K まで伸びます。Ai=0A_i = 0 の青木君がいないときは、最初のすき間に時刻 00 も含まれるので、高橋君が時刻 00 に押すことになります。

使用ライブラリ:cpp_include@9c33ee7