典型テクニックまとめ

いつも忘れるので整理してまとめるぞい

MathJaxで書いた　参考：MathJaxによる数式表示

数え上げ

• Bell Number: 区別できる n$n$ 個のボールを区別できない k$k$ 個以下の箱に分割する
  • 特に B(n,n)$B(n,n)$ は n$n$ 個のボールを任意個のグループに分割する方法の数である。
  • 怪しい　全射の個数の証明とベル数 | 高校数学の美しい物語　でしか見たことがない
  • wikipediaと定義が違う　ベル数 - Wikipedia
• Stirling Number (1st kind): n$n$ 個のボールを k$k$ 個の非空のsubsetに分割する通り数
  • x(x−1)(x−2)(x−3)…(x−n)$x(x-1)(x-2)(x-3)\dots (x-n)$ のk$k$次の係数とも取れる
• Montmort Number: 撹乱順列の個数 包除原理で求められる
• ソートして大きいものから考える
• 区間の端だけ求めると ∑(ri−li)$\sum (r_i-l_i)$ で求められる
• 候補の区間が複数ある場合は最長のものだけ考える
• ちょうど K$K$ 個 = (K$K$ 個以下) - ( K−1$K-1$ 個以下 )
• 全ての x∈G$x\in G$ に対し f(x)∈H$f(x)\in H$ を数えるとき、y∈H$y\in H$ に対し f−1(y)=x$f^{-1}(y)=x$ なるものを数えることもできる
• 多項式の係数のGCDは積に対して準同型をなす（ c(P)c(Q)=c(PQ)$c(P)c(Q)=c(PQ)$
• ∑(ij)$\sum (\genfrac{}{}{0ex}{}{i}{j})$の形は高速に求められることがある（黒白が X,Y$X,Y$ 枚あって、その中から L$L$ 枚選んで並べる）とか F - Card Game for Three
• 判定問題を考える（ある条件を満たすものは何通り？→与えられたものは条件を満たすか？）
• 状態を準同型でまとめる（和、差など）
• ∑a≥0,b≥0,a+b=cH(x,a)H(y,b)=H(x+y,c)$\sum _{a\ge 0,b\ge 0,a+b=c}H(x,a)H(y,b)=H(x+y,c)$ Problem - D - Codeforces
• 操作回数の期待値 = 各操作を行う回数の期待値の和 J - 動的無計画法 A - Erasing Vertices

グラフ

• 次数1の頂点を取り除く
• 次数が1の頂点を見る
• 平面上の包含関係は木構造になる
• 根付き木の同型判定は子をソートしながら()で囲うと O(N2logN)$O(N^2\log N)$ でできる
  • hashでやれば O(NlogN)$O(N\log N)$
  • D - 木、
• グラフをオイラー路に分割するときの最小の数は ∑vmax(iv−ov,0)$\sum _{v}max(i_v-o_v,0)$
• Oreの定理：任意の隣接しない二頂点の字数の和が頂点数以上ならハミルトン閉路が存在する
• Konigの定理：二部グラフの辺彩色は最大次数と一致する
• 辞書順最大の独立安定集合はgrundy数になる

木

• 根を固定した時、部分木のサイズが自分より大きくなる辺は根以外でちょうど一本存在する
• 部分木はオイラーツアーで一つの区間になる
• パスはHL分解で O(logN)$O(\log N)$ 個の区間になる
• 高さの和の部分和問題は上界と下界で挟める
• 高さが低いなら葉がたくさんある 参考: https://codeforces.com/contest/1104/problem/E
  • より形式的には、高さが h$h$ なら少なくともn−1h$\frac{n-1}{h}$個はある
• 各頂点の次数はプリュファーコードでの出現回数 + 1 になっている No.1302 Random Tree Score - yukicoder

構築

• へび
• 二べき
• 縦横でダメなら斜め Grand Prix of Nanjing - A
• 非対称なものを作りたいときは乱択する
• 二つ作って重ねる AGC025D, AGC027D

幾何

• 格子点のみを頂点とする図形の面積は 0.5$0.5$ 刻み（ピックの定理）
• 放物線をつなげて一番高いところに行きたい場合は終点の傾きを一致させる

ゲーム

• 小さい制約の問題をgrundyで解いてエスパーする
• DPできる制約ならする
• 不変量を考える

文字列

• ある文字列をずらして一致してる部分を最大化⇒FFT
• 辞書順最小を求める場合はprefixではなくsuffixでDPする
• distinctな文字列の数え上げは直近の文字にだけ遷移するようにすればできる AGC027E, ARC110E
• 辞書順最小のconcatはx+y<y+xでソート ECR9-C
• 文字列のソートは長さの総和を S$S$ とすると O(SlogS)$O(S\log S)$ でできる（STLでも）
• 文字列をいくつかの連続部分列に分けると独立に考えられる場合がある

最適化

• 最適解を持ってきて性質を見る
• 他の情報から復元できるパラメータを探す
• 自由度が一つ落とせる場合は半分全列挙ができる
• 極大と最大が一致するかを考える
• 順番を決める問題は適当な基準でソートして貪欲かDP
• 操作によっていくつかの区間に分かれ、それぞれが独立なものは区間DP
• f(X)$f(X)$ の最小化は X$X$ を決め打ったときの性質に注目する
• 最大値、最小値に注目する

オーダー改善

• ペア、トリオだけ考える
• 最初の一つを決めると残りも決まる
• 冪乗が出てきた場合、k=1を場合分けで取り除くとsqrtに落ちる
• 調和級数でlogになる（ ∑1K=NlogN$\sum \frac{1}{K}=N\log N$
• 個数制限付きナップザックは2冪に分解すると高々log個の01ナップザックになる
• 使わなかったものを最後にまとめて貪欲
• 配るDPをもらうDPに書き換えてセグ木で高速化
• 多次元DPでは一番小さいパラメータを動かす
• 部分集合の列挙は O(3n)$O(3^n)$ でできる（ for(int i=b;i>0;i=(i-1)&b);
• 同じ状態をまとめる
• 各要素が高々一つのときはbitDP
• 階差を考える
• 累積和をとる
• a>b$a>b$ なら (amodb)<a/2$(amodb)<a/2$
  • MODを取って結果が変化するのはlog回（毎回半分以下になるので）
• 累積和を k$k$つずらすのは O(k)$O(k)$ でできる
• Master Theorem
  • T(N)=aT(N/b)+f(N)$T(N)=aT(N/b)+f(N)$ の形の漸化式を満たす計算量の解析
  • 分割統治とマスター定理の紹介
  • a=b=2$a=b=2$ Problem - E - Codeforces
• 適当なポテンシャルを考えると償却できる
  • LCT が有名
  • B - Joker

定数倍改善

• setのlower_boundは遅いので変更がないならvectorを使う
• キャッシュの載り方を意識する
• 構造体を渡す時は参照渡しにする
• unordered_map, unordered_set
  • reserveすると100倍くらいかわる
• pb_ds_cc_hash_table

手抜き実装

• 番兵を入れると境界値判定が不要になる
• 手抜きしてもいいか実装前によく確認する
• 等価に思える処理が等価かどうかよく確かめる

デバッグ

• オーバーフローに気をつける
• 負数のMODを取ると負数になる
• string::find で見つからなかった時に帰ってくるのはstring::npos （-1とは限らない）
• printf ではちょうど1/2は切り捨てられる（+EPSすれば回避可能)
• std::lower_boundをsetに使うと O(N)$O(N)$

勘違い

• DAGでないグラフで最小値を求める場合はメモ化再帰ではなくDijkstra
• a -> c の最短路の長さと (a -> b の最短路の長さ)+(b -> c の最短路の長さ) は必ずしも一致しない
• フローでの頂点の流量は（自分で制限しないと）無限
• 次数が3以上のグラフでDFSで全探索は普通にやるとできない
  • 最後の子を探索するとき左の子の探索は最終状態しか残っていない
• 嘘解法を考えすぎない
• 乱択はよっぽどのことがないと通らない
  • 投げる前に確率を見積もる

未分類

• 単調性がないかどうか考える（あれば二分探索できる）
• 最小値の最大化、平均最大化は二分探索
• K番目の値を求める時はX以下の数を数える二分探索
• 入力を乱数で生成すると最悪ケースがなくなる
• 操作を繰り返す系は不変量に注目する
• マンハッタン距離の総和の最小化はn/2番目の値
• マンハッタン距離は回す！！
  • (x, y) → (x+y, x-y) とすればよい
• 中央値を求める時はペアを作る
• 逆から見る
• クエリを先読みする
• gcd(x, x+1) = 1
• BITはmapで動的に構築すると空間 O(QlogQ)$O(Q\log Q)$、時間 O(Qlog2Q)$O(Q{\log }^{2}Q)$
• 左右で分けてくっつける
• 各人が選択をするとき、同じ選択をする人をまとめて考える AGC022D
• 半分ずつになるDPのとき、幅は高々log個見ればいい
• 操作が可逆な時 A->Bにできる ⇔ B->Aにできる ⇔ A->C->Bにできる ⇔ A->C, B->Cにできる
• 行反転と列反転で01を全て同じ色にできる ⇔ 任意の小正方形(2x2)内のxorが0 ARC081D
• 関数は合成に関してモノイドをなす（セグ木に載る）
• yが一定なら max(floor(xy))=floor(max(x)y)$max(\mathrm{f}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{r}(\frac{x}{y}))=\mathrm{f}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{r}(\frac{max(x)}{y})$
• maxとfloorとaddは合成できる（遅延セグ木に載る） JAG
• 要素を[k, k+len) に並べるような場合はすべてのx座標からiを引いておく
• ある値xを作れるか⇔∑lb ≤ x ≤ ∑ub
• ある条件を満たすものが一つでもあるかという質問は、個数を求めると逆元を作れる dowango
• p進数での桁和と元の数はmod (p-1)で一致する
• 操作で順序が入れ替わらないことがある
• 可換な操作を全体に対して行うような操作は分割統治で順序関係を制限できる
• 和と差はmod2で不変
• xor に対して準同型なhash ってなーんだ？ zobrist hash
• 区間カウントクエリはMo Problem - D - Codeforces