beet's soil

競プロのことなど

典型テクニックまとめ

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

数え上げ
  • Bell Number: 最大クリークの数え上げ
  • Stirling Number: N個の数字をK個の非空のsubsetに分割する通り数
  • Montmort Number: 撹乱順列の個数
  • ソートして大きいものから考える
  • 区間の端だけ求めると  \sum r_i -l_i で求められる
  • 候補の区間が複数ある場合は最長のものだけ考える
  • ちょうどK個 = K個以下 - (K-1)個以下
  • 全てのx∈Gに対しf(x)∈Hを数えるとき、y∈Hに対しf^-1(y)=xなるものを数えることもできる
グラフ
  • 次数1の頂点を取り除く
  • 根付き木の同型判定は子をソートしながら()で囲うと  O(N^2logN) でできる
  • 平面上の包含関係は木構造になる
  • DAGでないグラフで最小値を求める場合はメモ化再帰ではなくDijkstra
  • 次数が1の頂点を見る
幾何
  • 格子点のみを頂点とする図形の面積は0.5刻み(ピックの定理)
ゲーム
  • 小さい制約の問題をgrundyで解いてエスパーする
文字列
  • ある文字列をずらして一致してる部分を最大化⇒FFT
  • 辞書順最小を求める場合はprefixではなくsuffixでDPする
オーダー改善
  • ペア、トリオだけ考える
  • 最大値、最小値だけ考える
  • 最初の一つを決めると残りも決まる
  • 他の情報から復元できるパラメータを探す
  • 冪乗が出てきた場合、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);
  • 順番を決める問題は適当な基準でソートして貪欲かDP
  • 階差を考える
  • 同じ状態をまとめる
  • 各要素が高々一つのときはbitDP
定数倍改善
  • setのlower_boundは遅いので変更がないならvectorを使う
  • キャッシュの載り方を意識する
  • 構造体を渡す時は参照渡しにする
  • unordered_map, unordered_set
手抜き実装
  • 番兵を入れると境界値判定が不要になる
  • 手抜きしてもいいか実装前によく確認する
デバッグ
  • オーバーフローに気をつける
  • 負数のMODを取ると負数になる
  • string::find で見つからなかった時に帰ってくるのはstring::npos (-1とは限らない)
  • printf ではちょうど1/2は切り捨てられる(+EPSすれば回避可能)
  • std::lower_boundをsetに使うと  O(N)
勘違い
  • a -> c の最短路の長さと (a -> b の最短路の長さ)+(b -> c の最短路の長さ) は必ずしも一致しない
  • フローでの頂点の流量は(自分で制限しないと)無限
  • 嘘解法を考えすぎない
その他
  • K番目の値を求める時はX以下の数を数える二分探索
  • 入力を乱数で生成すると最悪ケースがなくなる
  • yが一定なら  max(floor(\frac{x}{y})) = floor(\frac{max(x)}{y})
  • 操作を繰り返す系は不変量に注目する
  • マンハッタン距離の総和の最小化はn/2番目の値
  • 関数は合成に関してモノイド
  • 中央値を求める時はペアを作る
  • 逆から見る
  • クエリを先読みする
  • gcd(x, x+1) = 1
  • BITはmapで動的に構築すると空間  O(QlogQ) 、時間  O(Q log^2 Q)
  • 左右で分けてくっつける
  • 非対称なものを作りたいときは乱択する
  • 各人が選択をするとき、同じ選択をする人をまとめて考える
  • 半分ずつになるDPのとき、幅は高々log個見ればいい
  • 操作が可逆な時 A->Bにできる ⇔ B->Aにできる ⇔ A->C->Bにできる ⇔ A->C, B->Cにできる
  • 行反転と列反転で01を全て同じ色にできる ⇔ 任意の小正方形(2x2)内のxorが0