競プロ頻出数値表・公式集 / Tips集

サイズ $m$ の集合とサイズ $n$ の集合から合わせて $r$ 個を選ぶ方法は、全体の $m+n$ 個から $r$ 個を選ぶ方法に等しいという恒等式です。計算量削減の要になることが多々あります。

パスカルの三角形において、ある列に沿って足し合わせた和が斜め下の値に等しくなる性質です。区間和を定数時間で求める際に利用します。

全体からまず $k_1$ 個を選び、残りから $k_2$ 個、さらに残りから $k_3$ 個というように選んでいく過程に対応しています。

例えば「いくつかの操作を行って到達可能な盤面の数」を求める際、盤面から逆算して「常に一意な操作（例: 最も左上の違反箇所を直す操作）のみを遡ったときに得られるルート」だけを辿ることで、探索木を重複のない木構造に変化させることができる（逆検索法 / Canonical Path）。

ゲームの選択和とは、各手番で $1$ 以上 $N$ 個以下のゲームに着手するようなゲームを指す。

ゲームの結合和（Selective Compound）とは、毎手番で $N$ 個のゲームすべてに同時に着手するゲームのことである。いずれか $1$ つ以上のゲームで手が指せなくなった（終了盤面に達した）時点で全体のゲームが終了する。

局面 $G$ の遠隔度 $R(G)$ は、互いに最適な行動をとった場合にその局面からゲームが終了するまでの残り手数を表し、以下のように再帰的に定義される：

• $G$ が終了盤面の場合：$R(G) = 0$
• $R(G')$ が偶数となる遷移 $G \to G'$ が存在する場合：$R(G) = 1 + \min \{ R(G') \mid G \to G', R(G') \text{ は偶数} \}$
• $G$ が終了盤面でなく、$R(G')$ が偶数となる遷移が存在しない場合：$R(G) = 1 + \max \{ R(G') \mid G \to G' \}$

勝者（奇数手数で終わらせたい側）は最も早く終了する手を選んで最短で勝ちにいき、敗者（偶数手数にしたい側）は少しでも長引かせる手を選ぶため、最小値の遠隔度の偶奇を判定することで全体の勝敗が得られる。

ゲームの皇帝和（Autocratic Compound）とは、毎手番で $N$ 個のゲームのうち $1$ つを選んで $1$ 回以上連続して着手し、その他の $N-1$ 個のゲームそれぞれに対しては $0$ 回以上 $1$ 回以下着手するゲームのことである。

各後手必勝盤面 $G$ に対して定義される値 $l(G)$ は、後手必勝盤面同士の遷移における最大の長さを表し、以下のように定義される：

$$l(G) = \max \{ l(G') + 1 \mid G \to^+ G', G' \text{ は後手必勝盤面} \}$$ （上の記号は、自分一人のみで1回以上の着手によって到達可能な後手必勝盤面の全体を指す。ただし、$G$ から $1$ 回以上の着手によって到達可能な後手必勝盤面 $G'$ が存在しない場合は $l(G) = 0$ とする。）

この性質により、すべてのゲームが後手必勝盤面であるという条件下において、皇帝和は各ゲームの $l(G_i)$ を山の高さとみなした標準的な Nim に帰着される。

非負の整数値をとる確率変数 $X$ の期待値は、$E[X] = \sum_{k=1}^\infty P(X \ge k)$ と変形できます。これを活用して状態の計算を簡略化することが多々あります。

2進数での足し算の繰り上がりを $2(x \land y)$ が担当し、繰り上がらない部分を $x \oplus y$ が担当します。条件式変形の定番です。

参照：Nimber (Nim和を和、Nim積を積とした数体系は体をなす。)

具体的な例として、「配列 $A = (A_1, A_2, \dots, A_N)$ のすべての部分集合 $S$ について、その総和の $K$ 乗を足し合わせた値」を求める問題を考えます。

直感的に書くと、求めたいのは以下の値です。 $$ \sum_{S \subseteq \{1, \dots, N\}} \left( \sum_{i \in S} A_i \right)^K $$

ここで、和の $K$ 乗を母関数の形式 $\left( \sum_{i \in S} A_i \right)^K = K! [x^K] \prod_{i \in S} e^{A_i x}$ に置き換えると、式は次のように変形できます。

$$ \begin{aligned} \sum_{S \subseteq \{1, \dots, N\}} \left( \sum_{i \in S} A_i \right)^K &= \sum_{S \subseteq \{1, \dots, N\}} \left( K! [x^K] \prod_{i \in S} e^{A_i x} \right) \\ &= K! [x^K] \sum_{S \subseteq \{1, \dots, N\}} \prod_{i \in S} e^{A_i x} \quad \text{（係数抽出 $[x^K]$ と 総和 $\textstyle\sum$ の入れ替え）} \\ &= K! [x^K] \prod_{i=1}^{N} \left( 1 + e^{A_i x} \right) \quad \text{（分配法則による因数分解）} \end{aligned} $$

なぜ計算量が劇的に減るのか：
そのまま計算すると部分集合 $2^N$ 通りそれぞれについて和の $K$ 乗を計算する必要があり、$O(2^N \cdot N)$ の時間がかかります。
しかし、変換後の式では「各要素 $i$ を選ぶ（$e^{A_i x}$）か選ばない（$1$）か」の $2^N$ 通りの組み合わせの和が、$\prod_{i=1}^N (1 + e^{A_i x})$ という $N$ 個の多項式の積に展開（因数分解）されています。

必要な項は $x^K$ まで（$K+1$ 項分）で十分なため、各 $1 + e^{A_i x}$ を高次項を切り捨てながら掛け合わせる（分割統治や NTT などを利用する）ことで、$O(2^N)$ から多項式時間（$O(N K \log N)$ など）へ大幅に高速化できます。

$X > A$ のときは $A \bmod X = A$（不変）であり、$X \le A$ のときは $X \le \frac{A}{2}$ ならば $A \bmod X < X \le \frac{A}{2}$、$X > \frac{A}{2}$ ならば $A \bmod X = A - X < \frac{A}{2}$ となり、いずれにせよ半分未満になる。 したがって、各要素が実際に更新される回数は高々 $O(\log(\max A))$ 回である。Segment Tree などで「区間最大値 $\ge X$」の箇所のみに再帰的に走査・更新を行うことで、全体 $O((N + Q) \log N \log(\max A))$ で処理できる。

特に評価点が $x = 0, 1, \dots, N$ のように連続している場合、分母が階乗の積になり、分子の累積積を前計算しておくことで、通常 $O(N^2)$ かかる補間を $O(N)$ に落とすことができます。

【代表例】
1. 1次変換: $f(x) = ax + b \implies f(g(x)) = a_1(a_2 x + b_2) + b_1 = (a_1 a_2)x + (a_1 b_2 + b_1)$
2. クランプ関数: $f(x) = \min(\max(x + a, b), c)$（区間加算と区間 chmin / chmax の合成）
3. アフィン変換行列: ベクトルに対する操作を行列積にまとめる
遅延セグメント木の作用素（Lazy tag）として乗せる際、この「合成に関する閉包性」を満たすことが必須要件となる。

転倒数とはなにか？
転倒数とは、ある数列の中で「大小関係が逆転しているペアの個数」のことである。具体的には、ある数列において、$i < j$ であるにもかかわらず「$i$ 番目の要素 $> j$ 番目の要素」となっているようなインデックスの組 $(i, j)$ の総数を指す。
隣接する要素を1回スワップすると、数列全体の転倒数は必ず $+1$ または $-1$ される。目的の配列（完全にソートされた状態 = 転倒数 $0$）に到達させるためには、無駄なく $-1$ されるスワップを選び続けるのが最適であり、その結果「最初の状態の転倒数」がそのまま「必要な最小スワップ回数」となる。

その求め方は？
以下の手順で数列を変換し、その転倒数を求めることで計算できる。

1. 位置の対応付け： 配列Bの各要素が「Bの何番目（インデックス）にあるか」を記録する。
   ※重複要素がある場合： 配列内に同じ値が複数含まれる場合、A内での1番目の $k$ とB内での1番目の $k$ を対応付けるなどする。
2. 配列Cの作成： 配列Aの各要素を、ステップ1で求めた「向かうべきBでのインデックス」に置き換えた新しい数列 $C$ を作る。これにより、「Aの各要素が最終的にどの位置に行くべきか」を表す数列ができる。
3. 転倒数の計算： 作成した数列 $C$ の転倒数を求める。

たとえば、$A = [2, 3, 1, 4]$、$B = [4, 1, 3, 2]$ の場合、Bの要素のインデックスは {4:0, 1:1, 3:2, 2:3} となる。Aの要素をこれに置き換えて新しい数列 $C = [3, 2, 1, 0]$ を作成し、この数列 $C$ の転倒数を計算すると $6$ となり、これが最小スワップ回数となる。

文字列 $S$ を小数とみなせば、結局、$\frac{S}{1 - 10^{-|S|}}$ の比較となる。 これより、全順序であることが従う。

前から決定すると将来選ぶ文字列によって優先度が崩れるが、後ろから確定させれば $DP[i-1]$ が定数扱いになるため、$S_j$ を先頭に付けた文字列同士を比較するだけで部分構造最適性が成り立つ。

通常の整数表記では先頭の $0$ は省略するが、ここでは leading zeroを許容して桁数を固定する。 たとえば、007 と 012 はともに3桁の表現であり、 数字列としては 007 < 012、 整数としても $7 < 12$ となる。 一般に、同じ長さの数字列 $A=a_1a_2\cdots a_n$、 $B=b_1b_2\cdots b_n$ があり、 最初に $a_i \ne b_i$ となる位置が $i$ なら、 $a_i < b_i$ のとき必ず $\operatorname{val}(A) < \operatorname{val}(B)$ である。 これは $\operatorname{val}(A)-\operatorname{val}(B)$ の符号が、その最初の異なる桁によって決まるためである。

したがって、連結によって作られる文字列の長さをまず考えれば、 同じ桁数の候補については文字列の辞書順をそのまま整数の大小関係として 扱うことができる。

• 先頭からの割合: 任意の $1 \le i \le 2N$ において、$S_1, \dots, S_i$ のうち$\lceil i / 2 \rceil$ 個以上が「(」である。かつ、$S_1, \dots, S_{2N}$ のうちちょうど $N$ 個が「(」である。（※左から貪欲に構築する問題やDPの判定条件として頻出）
• 末尾からの割合: 任意の $1 \le i \le 2N$ において、後ろから $i$ 文字（$S_{2N-i+1}, \dots, S_{2N}$）のうち$\lceil i / 2 \rceil$ 個以上が「)」である。かつ全体の「)」が $N$ 個。（※文字列を後ろから走査する際に必須の条件）
• 累積和の最小値 ($\pm 1$ 変換): 「(」を $+1$、「)」を $-1$ とした数列の累積和 $A$ を考えたとき、$A_{2N} = 0$ であり、かつ全ての $i$ について $A_i \ge 0$ である。（※この累積和をセグメント木に乗せることで、「括弧の反転クエリ」や「区間整合性クエリ」に $O(\log N)$ で対応可能になる基本テクニック）
• 未マッチ括弧の縮約（隣接キャンセル）: 文字列から隣り合う「()」を消去する操作を繰り返すと、最終的に空文字列になる。また、いかなる部分文字列もこの操作を限界まで行うと必ず「))))((((」のように「閉じ括弧が連続した後に開き括弧が連続する」形になる。（※部分区間の括弧列の状態をマージするモノイドとしてセグ木に乗せる際の超重要性質）
• 非交差マッチング: 全ての「(」と「)」をペアにして結んだとき、各ペア $(u, v)$ ($u < v$) は $S_u =$「(」かつ $S_v =$「)」を満たし、さらにどの2つのペアの線も交差しない。（包含関係にあるか、完全に独立しているかのどちらかのみ。※区間スケジューリングや円環上の交差問題への帰着に有用）
• 一意な再帰構造 (文法): $S$ は空文字列であるか、あるいはある整合な括弧列 $A, B$ を用いて「(」+ $A$ +「)」+ $B$ という形に「一意に」分解できる。（※数え上げの区間DPや、カタラン数の漸化式 $C_N = \sum(C_i \times C_{N-i-1})$ を導出する際の基本構造）
• Dyck路（グリッド上の経路）: 「(」を右 ($x+1$)、「)」を上 ($y+1$) への移動とみなしたとき、原点 $(0,0)$ から $(N,N)$ へ至る最短経路のうち、直線 $y = x$ を一度も上に超えない（常に $x \ge y$）経路である。（※鏡像法によるカタラン数の組み合わせ的計算への帰着）
• 木のオイラーツアー（DFS軌跡）: $N+1$ 頂点の順序付き根付き木において、根からDFS（深さ優先探索）を行い、「辺を下るときに ( 」「辺を上るときに ) 」と記録して得られる文字列と一対一対応する。（※木の問題を括弧列の問題に変換し、LCA（最小共通祖先）をRMQ（区間最小値クエリ）で解くための基礎）
• 巡回シフトと最小値（Raneyの補題）: 「(」と「)」が $N$ 個ずつある任意の（整合とは限らない）括弧列に対し、$\pm 1$ の累積和が最小となるインデックスの直後で巡回シフト（分割して前後を入れ替える）すると、必ず整合な括弧列になる。（※「条件を満たすように切り出して構築しろ」といったアドホックな構築問題での必殺技）

一般に、（連続していない）LCSについては $O(|S||T|)$ で計算できるが、$|S|$ が重複する文字を持たないような文字列の場合には $O(|S| + |T|\log |T|)$ で計算できる。

DFSは「常に最も左の未探索枝」を優先して深さ方向に進むため、探索順序そのものが全体解の辞書順と完全に一致する。 DPで後続の最小値を保持して前から復元する方法に比べ、枝刈り（Pruning）と組み合わせやすく、状態や文字列の比較コストを考慮せずに $O(\text{探索頂点数})$ で解が得られる。

※ サイクルが存在しない森の場合は $L = 0$ となり、$C = V - E$ が成り立ちます。木の場合はさらに $C = 1$ なので $V - E = 1$ になります。

【固定した頂点から最も遠い頂点】 木 $T$ の頂点 $s$ を一つ固定したとき、直径の両端点を $u,v$ とすれば、そのいずれかは $s$ から最も遠い点になります。

同型判定において中心が2つ存在する場合は、両方の頂点をそれぞれ根としてハッシュを計算し比較するか、2つの中心を結ぶ辺の中点にダミー頂点を追加して唯一の中心（根）とみなす手法がとられます。

ある頂点 $u$ に注目し、生成された有向グラフでの出次数を $k$ とする（つまり、$u$ から $k$ 個の頂点に向かって有向辺が出ている）。

1. 向き付けのルール（次数が小さい方から大きい方へ向かう）より、$u$ が向いている先の $k$ 個の頂点はすべて、元の無向グラフにおいて次数が $\deg(u)$ 以上である。
2. $u$ 自身が出次数 $k$ を持つため、当然ながら元の無向グラフでの次数 $\deg(u)$ は $k$ 以上である（$\deg(u) \ge k$）。
3. したがって、$u$ の行き先である $k$ 個の頂点は、すべて元の無向グラフにおいて次数が $k$ 以上である。
4. ここで、グラフ全体の次数の総和は $2M$ である（握手補題）。
5. グラフ内には「次数が $k$ 以上の頂点」が少なくとも $k$ 個（$u$ の行き先の頂点群）存在することが確定した。これら $k$ 個の頂点だけで次数の和を計算しても $k \times k = k^2$ となる。

全体の次数の総和 $2M$ は、これら一部の頂点の次数の和 $k^2$ よりも必ず大きいため、 $$k^2 \le 2M$$ $$k \le \sqrt{2M}$$ が成り立つ。これにより、どのようなグラフであっても各頂点の出次数が高々 $O(\sqrt{M})$ に抑えられることが保証される。

各連結成分を1つの頂点に縮約した $n$ 頂点のグラフを考えます。成分 $i$ と成分 $j$ をつなぐ橋の選び方は $s_i s_j$ 通りあるため、これを辺の重みとみなして行列木定理を適用します。
全体の頂点数を $N = \sum_{i=1}^n s_i$ とすると、重み付きグラフのラプラシアン行列 $L$ は以下のようになります。

• 非対角成分 ($i \neq j$): $L_{ij} = -s_i s_j$
• 対角成分: $L_{ii} = \sum_{j \neq i} s_i s_j = s_i(N - s_i) = s_i N - s_i^2$

行列木定理より、求める木の総数は $L$ から $n$ 行目と $n$ 列目を取り除いた $(n-1) \times (n-1)$ の小行列 $L_0$ の行列式 $\det(L_0)$ に等しくなります。
対角行列 $D = \mathrm{diag}(s_1 N, \dots, s_{n-1} N)$ と、ベクトル $\mathbf{s} = (s_1, \dots, s_{n-1})^T$ を用いると、$L_0 = D - \mathbf{s}\mathbf{s}^T$ と表せます。
行列式補題（$\det(A - uv^T) = \det(A)(1 - v^T A^{-1} u)$）を用いると、計算は次のように鮮やかに展開されます。 $$ \det(L_0) = \det(D) \left( 1 - \mathbf{s}^T D^{-1} \mathbf{s} \right) $$ $$ = \left( \prod_{i=1}^{n-1} s_i N \right) \left( 1 - \sum_{i=1}^{n-1} \frac{s_i^2}{s_i N} \right) $$ $$ = N^{n-1} \left( \prod_{i=1}^{n-1} s_i \right) \left( 1 - \frac{N - s_n}{N} \right) $$ $$ = N^{n-1} \left( \prod_{i=1}^{n-1} s_i \right) \left( \frac{s_n}{N} \right) = N^{n-2} \prod_{i=1}^n s_i $$

各頂点の次数 $d_i$ が指定された木を数え上げる問題は、Prüferコードの性質により「長さ $N-2$ の数列に、各要素 $i$ を $d_i - 1$ 個ずつ配置する順列の総数」に帰着されます。この総数は多項係数 $\frac{(N-2)!}{\prod_{i=1}^N (d_i-1)!}$ を用いて $O(N)$ で計算可能です。

頂点 $u$ の遷移先を探す際、未訪問頂点集合を走査しながら「$u$ の隣接リストに含まれる頂点」であればスキップし、「含まれない頂点」であればキューに追加して未訪問集合から削除する。 スキップが発生する回数の総和は元のグラフの辺数 $2M$ で抑えられるため、全体計算量は std::set を用いた場合 $O((N + M) \log N)$ となる。

一般のグラフでは、最大マッチングの大きさと最小頂点被覆の大きさは必ずしも一致しないが、 2部グラフでは必ず一致する。そのため、最大マッチングを求めると、 同じ大きさの最小頂点被覆も構成できる。

特に、最大マッチング $M$ を求めたあと、 $U$ の未マッチ頂点からマッチング辺と非マッチング辺を交互にたどって到達可能な頂点集合を $Z_U, Z_V$ とすると、 $$ (U \setminus Z_U) \cup Z_V $$ が最小頂点被覆になる。 したがって、「最大マッチングを求める問題」と「最小頂点被覆を求める問題」が 2部グラフでは同じ値を持つという点が重要である。

また、Hallの結婚定理が「完全マッチングが存在する条件」を与えるのに対し、 Kőnigの定理は「最大マッチングの大きさ」と 「すべての辺を覆うために必要な最小頂点数」の関係を与える定理である。 競プロでは、2部マッチングを求めたあとに最小頂点被覆そのものを復元したい場合や、 マッチング問題を別の被覆問題へ変換する際に利用される。

例えば、頂点集合 $S \subseteq V$ について、$S$ に含まれる異なる任意の2頂点の間に 辺が存在しなければ、$S$ は独立集合である。 「互いに直接つながっていない頂点を、できるだけ多く選ぶ」と考えるとよい。

最大独立集合と最小頂点被覆には補集合による重要な関係がある。 任意のグラフについて、 $$S\text{ が独立集合} \iff V\setminus S\text{ が頂点被覆}$$ が成り立つため、 $$\boxed{ \text{最大独立集合の大きさ} = |V|-\text{最小頂点被覆の大きさ} }$$ となる。

さらに、2部グラフではKőnigの定理より、 $$\text{最大マッチングの大きさ} = \text{最小頂点被覆の大きさ}$$ が成り立つ。したがって、 $$\boxed{ \text{最大独立集合の大きさ} = |V|-\text{最大マッチングの大きさ} }$$ となる。

つまり2部グラフでは、 最大マッチングを求めることで、最大独立集合の大きさも求められる。 さらに、最大マッチングから到達可能頂点集合を復元すれば、 最大独立集合そのものも構成できる。

最大マッチング $M$ に対して、左側の未マッチ頂点から交互道をたどり、 到達可能な頂点集合を $Z_U, Z_V$ とすると、 $$\boxed{ Z_U \cup (V\setminus Z_V) }$$ が最大独立集合になる。

競プロでは、問題文に「互いに隣接しない頂点を最大数選ぶ」といった条件が現れたとき、 それが2部グラフなら、最大独立集合 → 最小頂点被覆 → Kőnigの定理 → 最大マッチング という変換を考えるとよい。

「いくら流せるか」の最大値は、ネットワークを2つに分断する最も狭いボトルネック（カット）の容量で決定する。競プロでは、制約を満たすためのコスト最小化問題をグラフの「最小カット」に帰着して解く（いわゆる「燃やし埋め」など）際のアプローチとして多用される。

鎖とは任意の2要素が比較可能な部分集合、 反鎖とは異なる任意の2要素が比較不能な部分集合を表す。

半順序集合の大小関係を二部グラフに帰着させる事を考える。 具体的には、頂点を倍加し、x > y なる組に対して、L_x から R_y へと辺を貼る。 このようにして得られたグラフの最大独立集合が最大反鎖長である。