beet's soil

競プロのことなど

典型テクニックまとめ

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

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

数え上げ

  • Bell Number: 区別できる $ n $ 個のボールを区別できない $ k $ 個以下の箱に分割する
  • Stirling Number (1st kind): $ n $ 個のボールを $ k $ 個の非空のsubsetに分割する通り数
    • $x(x-1)(x-2)(x-3) \ldots (x-n)$ の$k$次の係数とも取れる
  • Montmort Number: 撹乱順列の個数 包除原理で求められる
  • ソートして大きいものから考える
  • 区間の端だけ求めると $ \sum r_i -l_i $ で求められる
  • 候補の区間が複数ある場合は最長のものだけ考える
  • ちょうど $ K $ 個 = ($ K $ 個以下) - ( $ K - 1 $ 個以下 )
  • 全ての $ x \in G $ に対し $ f(x) \in H $ を数えるとき、$ y \in H $ に対し $ f^{-1}(y) = x $ なるものを数えることもできる
  • 多項式の係数のGCDは積に対して準同型をなす( $ c(P) c(Q) = c(P Q) $
  • $ \sum{ \binom{i}{j} } $の形は高速に求められることがある(黒白が $X, Y $ 枚あって、その中から $L$ 枚選んで並べる)とか F - Card Game for Three
  • 判定問題を考える(ある条件を満たすものは何通り?→与えられたものは条件を満たすか?)
  • 状態を準同型でまとめる(和、差など)
  • $ \sum_{a \ge 0, b \ge 0, a + b = c} H(x, a) H(y, b) = H(x + y, c) $ Problem - D - Codeforces

グラフ

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

  • 根を固定した時、部分木のサイズが自分より大きくなる辺は根以外でちょうど一本存在する
  • 部分木はオイラーツアーで一つの区間になる
  • パスはHL分解で $ O(\log N) $ 個の区間になる
  • 高さの和の部分和問題は上界と下界で挟める
  • 高さが低いなら葉がたくさんある 参考: https://codeforces.com/contest/1104/problem/E
    • より形式的には、高さが $h $ なら少なくとも$ \frac{n-1}{h} $個はある

幾何

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

ゲーム

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

文字列

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

最適化

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

オーダー改善

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

定数倍改善

  • 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)

勘違い

  • 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) 、時間 [tex: O(Q log2 Q) ]
  • 左右で分けてくっつける
  • 非対称なものを作りたいときは乱択する
  • 各人が選択をするとき、同じ選択をする人をまとめて考える
  • 半分ずつになるDPのとき、幅は高々log個見ればいい
  • 操作が可逆な時 A->Bにできる ⇔ B->Aにできる ⇔ A->C->Bにできる ⇔ A->C, B->Cにできる
  • 行反転と列反転で01を全て同じ色にできる ⇔ 任意の小正方形(2x2)内のxorが0
  • 関数は合成に関してモノイドをなす(セグ木に載る)
  • yが一定なら  max(floor(\frac{x}{y})) = floor(\frac{max(x)}{y})
  • maxとfloorとaddは合成できる(遅延セグ木に載る)
  • 要素を[k, k+len) に並べるような場合はすべてのx座標からiを引いておく
  • ある値xを作れるか⇔∑lb ≤ x ≤ ∑ub
  • ある条件を満たすものが一つでもあるかという質問は、個数を求めると逆元を作れる
  • p進数での桁和と元の数はmod (p-1)で一致する
  • 操作で順序が入れ替わらないことがある
  • 可換な操作を全体に対して行うような操作は分割統治で順序関係を制限できる
  • 和と差はmod2で不変
  • xor に対して準同型なhash ってなーんだ? zobrist hash
  • 区間カウントクエリはMo Problem - D - Codeforces