競技プログラミング　典型問題メモ - かんプリンの学習記録

最終更新日 2024/01/07

競技プログラミングにおける典型知識や問題を書いていきます.
AtCoderなどで出た問題で, 分からなかったり面白かったりしたものが多め.

桁DP
部分列DP
全方位木DP
bitDP
箱根駅伝DP
挿入DP
区間DP
AlienDP
2乗の木DP
インラインDP(in-place DP)
bitsetによる定数倍高速化
複数の頂点間の辺の張り方
木の性質
XOR(排他的論理和の)性質
包除原理
ゼータ変換・メビウス変換・アダマール変換
区間に対する演算
形式的冪級数
ダブリング
不変量に注目する
Mo's algorithm
期待値の線形性
ProjectSelectionProblem(燃やす埋める)
2-SAT
Subset Convolution
逆元の前計算ができない二項係数
Slope Trick
Weighted-Union Heuristic
掃き出し法
ポリアの数え上げ定理
Hallの結婚定理
Baby-step Giant-step
積の和典型
HL分解
Stern-Brocot Tree
その他

桁DP

[桁][未満フラグ]を持ちながら行うDP

★はオートマトンDPで解いたやつ(ついてないから解けないというわけではない)

複数のやつ

他

未分類(後で分類する) - CF861 C - yukicoder 2483

部分列DP

全方位木DP

木のすべての頂点について, その頂点を根としたときの木DPを高速に行う.

bitDP

集合を情報として持ちながら行うDP.
制約で分かる

箱根駅伝DP

条件を満たす順列を数え上げる問題で「どこまで見たか」,「割り当ててないものの数」とかをもってDPするやつ

AOJ 2439 (名前の由来)
ABC134 F
ABC309 G

挿入DP

箱根駅伝DPと同様に順列についての問題でよく使う手法.

AlienDP

位置と操作回数をもつようなDPだと ${O(N^2)}$ かかるが，これがある性質を満たすなら二分探索を用いて ${O(N\log{N})}$ なるというもの．Alien Trickとも言ったりする．参考1 参考2 参考3

Mongeグラフ上のd-辺最短路長を計算するアルゴリズム

二分探索しないやつ

CodeQueen2023 E

2乗の木DP

${O(n^3)}$ じゃね？と思いきや ${O(n^2)}$ ですというDP

インラインDP(in-place DP)

更新箇所が限定的である場合にDP配列を使いまわすことで計算量を削減するDP

bitsetによる定数倍高速化

ナップサックDPなどはbitsetによって計算量が ${\frac{1}{64}}$ くらい落ちる

複数の頂点間の辺の張り方

https://www.slideshare.net/secret/r8gjH9xYxFR0Fu 区間に辺を張る① 区間に辺を張る②

木の性質

木とは連結かつ閉路のない単純グラフのこと.

以下の条件は同値である.

グラフ ${T}$ は頂点数 ${N}$ の木である.
${T}$ は連結で,辺の数が ${N-1}$ の単純グラフである.
${T}$ は閉路がなく,辺の数が ${N-1}$ の単純グラフである.
${T}$ の任意の辺は橋である.
${T}$ の任意の二点を結ぶパスは一つである.
${T}$ の隣接していない二点を辺で結ぶとちょうど一つの閉路ができる.

複数の木からなるグラフを森と呼ぶ.

森の頂点数, 辺数, 連結成分数の間には以下のような関係がある.

頂点数 ${=}$ 辺数 ${+}$ 連結成分数

AGC015 C

XOR(排他的論理和の)性質

XORには様々な性質がある.

${x\oplus x=0}$
${x\oplus y=y\oplus x}$
${x}$ が偶数ならば ${x\oplus (x+1)=1}$
${x+y=x\oplus y+2×(x \rm{and} y)}$
${x\oplus z=y\oplus z \Leftrightarrow x=y}$
${x\oplus z=y\Leftrightarrow x=y\oplus z}$
${x\oplus y+x \, {\rm{and}} \, y=x \,{\rm{or}}\, y}$

包除原理

ゼータ変換・メビウス変換・アダマール変換

集合の上位/下位の集合に対しての和をとったり, それを戻したりするのを高速にしてくれるやつ. これを利用して畳み込みとかできる.

約数系

区間に対する演算

ある区間に対して演算(和など)を行うときには, 隣り合う要素の差を見ると区間の端に対しての操作のみ行えばよいことになるので高速化できることがある.

形式的冪級数

組み合わせを含めた様々な問題を機械的に解けるので強そう.

参考

隣り合う要素が異なるという条件付きの数え上げ

ダブリング

1つ次のもの(状態)が簡単に求められるとき ${K}$ つ先のものを高速に求める手法

不変量に注目する

ある操作を行うとき，操作前と操作後で変わらないものを見ると分かりやすく言い換えることができることがある．

Mo's algorithm

区間に関するオフラインクエリをいい感じに処理するやつ解説あり

部分木はオイラーツアーパスはhttps://codeforces.com/blog/entry/43230

rollbackできれば挿入だけでいい

期待値の線形性

ProjectSelectionProblem(燃やす埋める)

選択にコストがあり，選択間にもコスト(制約)がある場合にうまくグラフを作ることで最小カットに帰着される． 2部グラフの最小頂点被覆はPSPの特殊な例なので最小頂点被覆問題もリストに含まれるかも

2-SAT

充足可能性問題の特殊な場合．複数の2択とその選択の間に不可能という関係があるような問題を解くときに使ったりする．

Subset Convolution

全ての ${S}$ に対して， ${h(S)=\sum_{T\subseteq S}f(T)g(S\backslash T)}$ を ${O(N^{2}2^{N})}$ で計算する．

逆元の前計算ができない二項係数

mod3とかmod合成数とかではフェルマーの小定理を用いた階乗の逆元の前計算による二項係数の計算ができない．その場合，modの素因数ごとに数をカウントしていく．例としてmod10の場合を考える． ${\frac{100\cdot 99\cdot 98\cdot 97\cdot 96}{5\cdot 4\cdot 3\cdot 2\cdot 1}}$ の分子は ${(2,5)}$ で ${(8,2)}$ 回割り切れ，分母は ${(3,1)}$ 回割り切れる．すべての素因数で(分子)>(分母)となっている場合，mod10で0になる．そうでない場合普通に計算する．