数え上げテクニック集
数え上げテクニック集
2 状態をまとめる
状態を同一視することで高速化する
まとめられる条件
遷移先状態が同じ
遷移につく係数が同じ
まとめられた状態すべてが問題文の条件を満たすか満たさないかのどちらか
3 探索順の変更
3.1 大きい順に並べる
3.2 順列は挿入DP
DPで順列を決める場合「何を既に使ったか」を管理する必要がある
小さければbit DPという手もある
並び順でやるのではなく、入れるものを昇順/降順でやる
3.3 区間は終点でソート
4 条件の言い換え
5 greedy からの帰着
「操作で作られる可能性のある列の個数を求めよ」は複数の操作列で同じ列が作られる時に難しい
産物から操作列を一意に定める方法があれば数えやすくなる
6 場合分けのテクニック
パラメータで場合わけ
disjointになるように注意
7 線形和への分解
僕が演算順序の変更と呼んでるものに近い
8 部分群のテクニック
不変量の数の予想
偶数なら偶奇の不変量がありそう
9 再帰的な定義の利用
DPと相性がいい 再帰的定義→DP
10 桁DP について
11 高速化のテクニック
11.1 累積和の利用
11.2 データ構造の利用
11.3 配列の使いまわし
11.4 高速フーリエ変換
11.5 高速ゼータ変換
結合法則と交換法則を満たす演算に使える
11.6 And と Add の畳み込み
高速フーリエ変換と同様のアルゴリズム
11.7 簡単な枝刈り
12 行列を用いたテクニック 26
12.1 二分累乗
コンパニオン行列の累乗
多項式の累乗
12.2 行列式のテクニック
13 小さい確率を無視する 29
14 二項係数のテクニック 30
14.1 頻出公式集
14.2 経路数への帰着
二項係数を経路数に帰着すると式変形が楽
14.3 45度回転
14.4 カタラン数
15 包除原理 33
15.1 対称性を用いる場合
15.2 DP を用いる場合
15.3 約数系包除
16 「解けない問題」を見極める
Related Pages
- →二分累乗法×モノイド的構造を見つけて二分累乗×うまい変形で除算を回避する×abundance_で殴る×素数の_abundance×tonelli-shanks_のアルゴリズム×ルジャンドル記号×平方剰余の相互法則×2_次体×有限体×フロベニウス写像×lehmer_のアルゴリズム×cipolla_のアルゴリズム×高速フーリエ変換×フェルマーの小定理×巡回群構造を用いた特殊な畳み込み×1_の_2^k_乗根_mod_p_を用いた畳み込み×ペル方程式×単項イデアル整域→
- →指数時間アルゴリズム×岩田_陽一×巡回セールスマン問題×最大クリーク問題×幅×グリッドグラフ×pathwidth×半分全列挙×最大独立集合問題×fptアルゴリズム×最小頂点被覆問題×有界探索木×カーネライズ×シュタイナー木問題×包除原理×ハミルトンパス×グラフ彩色問題×彩色数×高速ゼータ変換×畳込み×完全マッチングの個数×完全マッチング×color_coding×k-cycle×bandwidth×cut_&_count×iterative_compression→
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×unionfind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
- →past5×past202012×アルゴリズム実技検定×past過去問練習202012×past5e×past5f×past5g×past5h×past5i×past5j×PAST5K×past5l×past5m×past5n×past5o×番兵×地図読み込み時に番兵をつける×ゴールをスタートにする×ゴールを一つにする×ダイクストラ法×bit_dp×期待値dp×二次元の片方を時間軸にする×past2n→
- →帰着する力×小さい制約の問題×nが8前後の制約×nが10~20前後の制約×n_が_30~40前後の制約×n_が_50前後の制約×n_が_300~500前後の制約×n_が_1000_前後の制約×小さな定数に注目×変数を一つ固定する×3つのものの真ん中を固定×行列の半分×xとyにわける×操作の不変量に注目×偶奇に注目×偶奇で場合わけ×操作の順番によらない×時間軸反転×元に戻せる操作×左右から累積積×等差数列の加算は差に注目×区間反転の合成はxor×grundy数×余事象を引く×k番目の数を二分探索×xorは繰り上がりのない足し算×xorは桁ごとに分割可能×45度回転×差の最小化は中央値×代表的なグラフで考察×木は二部グラフ×木の直径×最大化を二分探索で×選択肢が少ない方から貪欲×二次元座標を二部グラフにする×順序を有向グラフにする×凸関数の極値は三分探索×単調増加ならしゃくとり法×等比数列は剰余に注目×n進数は剰余に注目×括弧列は上り下り×競技プログラミングで解法を思いつくための典型的な考え方×keyence2020 d×abc152 f×agc026_c×arc060_a×joi2008ho_c×abc034d×abc138e×abc023d→
- →ホッケースティック恒等式×二項係数の公式×Vandermondeの恒等式×巨大なnについての二項係数×形式的べき級数×arc110d_fps×oeis×重複組合せの畳み込み×arc110d_nonfps×arc110→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]