典型タグ
定義から使う場面を確かめ、タグ名から手掛かり・単元・問題へ進めます。
期待値の頻度圧縮と加法的ポテンシャル
種類名に関する対称性を使い、高次元の期待残り費用を頻度別関数の和へ分離する。一種類の一段方程式を自己ループも含めて解き、終端で定数を較正する。
加法的tree metric復元
全点対距離行列の加法性から葉の接続先とedge長を決め、候補木の全距離を再計算して存在を完全検証する。
Aho–Corasick
複数patternのTrieへfailure linkとoutput情報を加え、最長接尾辞状態を文字ごとに更新する。
単調進行による償却解析
要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑える。
automaton上のDP・行列遷移
位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。
非決定性automatonのsubset construction
同時に存在し得るNFA状態集合を一つのDFA状態とし、文字ごとの集合遷移と受理条件を構成する。
Baby-Step Giant-Step・可逆作用の反復到達探索
有限群の累乗または有限集合上の可逆写像fについてf^t(s)=gをt=iB+jへ分け、target側のinverse baby stepとstart側のgiant stepをhash照合して到達時刻を平方根時間で求める。
backtracking・可逆な探索状態
再帰へ入る直前に局所選択を反映し、復帰時に必ずundoして現在pathだけの制約を保ちながら探索木を列挙する。
一次元凸・単峰最適化
差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。
Bézout等式・一次不定方程式
整数線形結合がgcdの倍数全体になることを使い、一次不定方程式の可解性と解のparameter表示を得る。
doubling・binary lifting
決定的遷移の2^k回後と累積値を合成し、巨大回数のjumpを二進分解で求める。
binary Trieによるbit列索引
整数を上位bitから分岐するTrieへ格納し、XOR・大小・距離条件に合う候補をbitごとに選ぶ。
二部matching・Hall・Kőnig
左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。
二部グラフの彩色と成分構造
無向グラフを二色に塗れる条件を探索で検証し、各連結成分の二部サイズ・反転対称性を集約する。
bitsetによるword並列集合演算
真偽集合をbit列へ詰め、交差・和・shift・popcountをword単位で実行して遷移や組数計算を加速する。
bitwise greedyによるmask最適化
上位bitから候補maskを仮定し、残り問題のfeasibility oracleでそのbitを保持/除去できるか決める。
上位bitの支配関係によるXOR minimax
最大XORを最小にする共通maskを求めるとき、最上位bitで値を二群へ分ける。一群だけならそのbitを相殺し、両群なら最大値のそのbitは必ず1なので、どちらの群を最大側にするかを再帰的に比較する。
Bostan–Mori・有理生成関数の係数抽出
P(x)/Q(x)のN次係数をQ(-x)との積の偶奇係数へ半減し、対数段で巨大indexへ進む。
有界全列挙・有限case分解
制約や生成パラメータから候補総数を界すか、鳩ノ巣原理で成功前の失敗回数を界して探索する。
繰り上がり・混合基数DP
整除鎖の丸め、支払いと釣銭、複数項の加算を下位桁から処理し、次の桁へ渡すcarry・borrowだけを状態に保つ。
Cartesian treeによる区間極値分解
配列順と値のheap順を同時に保つ木を構成し、区間極値を根とする再帰分割へ変換する。
組合せ係数・数え上げ
選択順・順列・分配を二項係数や階乗と対称性で式化する。
組合せ・多項式・線形代数への変換
数え上げや遷移を係数列・多項式・線形写像へ変換する。
構成解・witness復元
成立条件の証明が与える局所操作やparentを記録し、実際の解を復元する。
寄与の数え上げと順序交換
数える対象を要素・組・値・区間ごとに一意に固定し、その対象を含む選択の個数や指示変数の期待値を先に集計する。
凸包・支持方向・境界候補
内部点が線形/凸目的に不要なことを示し、orientation順で凸境界を構成して支持方向ごとの極値を得る。
Convex Hull Trick・直線包絡
一次関数の候補を傾き・交点順に管理し、各query点で最小または最大となる直線を選ぶ。
畳み込み・相互相関
係数積和または反転列とのcorrelationを多項式積へ写し、必要な次数範囲をNTT/FFTで計算する。
独立な数ゲームの和
全ての後続局面が数で、左選択肢の全値が右選択肢の全値より小さいことを確認し、その間の最も単純な二進有理数を局面値とする。独立和は厳密な数の加算で評価する。一般のpartisan gameは数とは限らず、この規則を適用しない。
座標・値の順序保存圧縮
疎な初期値・将来更新値・event座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写す。
cycle space・fundamental cycle basis
無向graphで全頂点が偶数次数となる辺集合をF_2上のcycle space C(G)として扱い、連結成分数C、spanning forest F、各non-tree edge eが作る唯一のcycleからfundamental cycle basisとdim C(G)=M-N+Cを導く。連結graphではC=1なのでM-N+1となる。
巡回群の指数化・位数別数え上げ
巡回部分群の元を指数へ写し、gcd・位数・約数格子で分類して重複なく数える。
循環局面の後退解析とminimax距離
終了局面から逆辺を辿り、終了側が一手選べば確定するOR局面と全手の確定を待つAND局面を区別する。未確定局面で無限継続を判定し、非負重みなら優先度付きキューで有限なminimax距離を確定する。
円環順序・chord交差
円周上の端点順をcutで線形化し、二chordの端点交互配置またはlaminar括弧構造として交差を判定・数え上げる。
DAGのtopological processing
依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。
指定次数parityの部分グラフ構成
選択辺集合の奇数次数頂点を指定し、spanning forestの葉から必要辺を確定してT-join型の構成を行う。
削除・縮約recurrence
辺を削除する場合と縮約する場合へ対象を分け、graph polynomialや連結構造のrecurrenceを立てる。
行列式による数え上げ
非交差経路やspanning treeなどの組合せ対象を行列式に対応させ、LGV補題・行列木定理で数える。
difference constraints・不等式系の最短路化
差の上界 x_v-x_u≤c を有向辺 u→v の重みcへ写し、Bellman–Ford等の緩和と負閉路から可解性・極値・具体解を求める。
上限制約付き桁DP
数値上限以下の桁列を接頭辞から構成し、tight・started・剰余・digit maskなど将来に必要な有限統計を保つ。
有向cycle検出・sink/source peeling
三色DFSのrecursion stackまたは入次数・出次数零の反復削除により有向cycleを検出し、必要ならcycleへ到達するcoreと処理可能なDAG部分を分離する。
有向walkの周期・cycle差分gcd
往復可能領域でedgeごとのdepth差を集め、そのgcdをclosed walk長の周期として巨大歩数の到達可能性を判定する。
方向別grid scanによる長距離効果の前計算
各行・各列を効果の向きにscanし、最後のblockerまたはactive emitterだけを保って、直線状に続く監視・照射・到達禁止効果を全体線形時間で印付ける。
約数格子のzeta・Möbius反転
約数/倍数方向の累積値とexact gcd・period値をnumber-theoretic Möbius関数または格子反転で相互変換する。
区間拡張DP
訪問済み範囲と現在いる端を状態にし、未訪問の左右の隣点へ拡張する。
prefix分割DP
列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。
DPの最小十分状態
将来の選択肢と答えが同じprefixを同一状態に縮約する。
DP状態と遷移
未来に必要な情報を状態とし、遷移と基底を設計する。
DP遷移の集約・高速化
同じ形の遷移をprefix、単調構造、剰余類などでまとめる。
DSUによる連結成分管理・縮約
辺追加や同値関係をDSUで統合し、成分代表と必要な成分metadataを一貫して保つ。
DSU merge tree・Kruskal reconstruction tree
成分併合ごとに新しい親nodeを作り、併合時刻・threshold・成分包含を一つのrooted treeへ記録する。
動的な区間和集合長
区間の追加・削除に応じて被覆の重複を保ち、現在の和集合の長さを更新する。Inventoryで特定されていない実装backendを前提にしない。
法上の動的積・剰余 0 因子の分離
取り得る因子のうち法 m で非零となるものがすべて可逆であることを確認し、因子の差し替えを「剰余 0 の因子数」と「非零因子の積」に分け、可逆な旧因子を逆元で外して新因子を掛ける。
動的・implicit Segment Tree
巨大または疎な座標域で訪れたnodeだけを生成し、区間要約と境界探索をO(log U)で保つ。
編集距離・sequence alignment DP
二つの列prefixを状態にし、一致・挿入・削除・置換の局所遷移から最小編集費用を求める。閾値がある場合は長さ差の下界で対角帯へ状態を絞る。
端点更新型のrun分割管理
順序付きのrun分割をdequeや連結リストで保持し、両端からの削除・分割・追加を行う。左端順setを使うODTとは区別する。
格子点転置によるfloor_sum
一次式の床和を格子点数とみなし、整数部分の取り出しと領域の転置でEuclid互除法型に再帰する。商一定区間の列挙とは異なり、傾きと法の交換が計算量を決める。
BEST定理によるEuler circuit数え上げ
有向Euler graphのcircuit数をrooted arborescenceの行列式と各頂点の出辺順列へ分解して数える。
Euler trail・circuit
全辺を一度ずつ使うEuler trail・circuitについて、無向graphの奇数次数条件または有向graphの入出次数条件と辺を持つ部分の連結性から存在を判定し、具体的な辺列が必要ならHierholzer法で構成する。
event・値順のオフライン走査
値・時刻・座標順にeventを並べ、同値eventの処理順を定めてactive集合や集約を増分更新する。
大容量unbounded knapsackのeventual linearity
最大密度item以外の総使用量を剰余と交換論で有限に界し、小容量prefixだけをDPした後の巨大capacityを基準itemの反復で埋める。
Fenwick Tree・反転数・重み付き接頭辞統計
値や座標の頻度を動的な接頭辞和で数えて反転数を求めるか、複数本を組み合わせて次数付きの区間式を評価する。
拡大有限体の表現と演算
素体上の多項式剰余または基底座標で有限体の元を表し、標準化された加減乗除を構成する。
標数pのFrobenius恒等式による反復高速化
標数pで中間の二項係数が消える恒等式 (1+x)^(p^t)=1+x^(p^t) をシフト演算へ適用し、隣接和反復をpの冪回ずつ飛ばす。圧縮列では各段のrun数の増加も評価する。
有限体部分空間のrank別計数
有限体上の部分空間をrankごとに分類し、Gaussian binomial係数などでspan条件を数え上げる。連立方程式を解く技能とは区別する。
有限関数・作用の合成
小さな有限集合上の関数を遷移表として表し、適用順を保ってprefix・区間の作用を合成する。
有限状態automatonの構成
文字を一つ加えた後の未来の挙動が等しい履歴を有限状態へ同値化し、pattern suffix・部分列進行・圧縮DP rowなどから全文字の完全遷移表を構築する。
下限制約付きflowの実現可能性
各辺のlower boundを先に流して頂点需要へ変換し、super source/sinkを加えたcirculationの飽和可能性を判定する。
形式的べき級数の基本演算
定数項条件と次数打切りを確認し、Newton iterationでinverse・log・exp等を畳み込みへ還元する。
FPS合成・power projection
多項式/FPSのcompositionとその転置であるpower projectionを、block分割・transposition・rational functionへ還元する。
fractional programming・比率parametric search
比率目標xに対して各寄与をbenefit-x·costへ変換し、和が非負かという単調な加法最適化へ帰着する。
frontier/profile DP・境界状態圧縮
走査済み領域と未走査領域の境界だけに未来へ影響する色・値の使用済みフラグ・接続partitionを保持し、必要なら同値な接続ラベルを正規化して幅指数で遷移する。
関数グラフのcycle・tree分解
各頂点の後続が一意なgraphをcycleと流入treeへ分解し、前周期・周期を処理する。
game状態・Grundy DP
各状態の勝敗またはGrundy数を後続状態から求める。
偶奇不変量によるゲーム戦略
後続局面をDPで列挙せず、合法手の独立な消費や終端状態の偶奇不変量を証明して、先手・後手の勝敗を決める。
有限局面DAGのminimax
必ず終了するゲームの局面DAGで、終端利得と各手番の最大化・最小化から局面値を求める。
Gaussian整数・二平方和
Z[i]での素因数分解と共役を用い、整数の二平方和表現をprime exponentごとに構成・数え上げる。
gcd不変量・差分構造
差・周期・range条件に共通するgcd不変量を抽出し、共通因子や剰余classを分離する。
母関数方程式・高度な係数抽出
暗黙方程式の反転、微分恒等式の係数比較、Euler積の疎な展開を使い分け、必要次数の係数を求める。
生成関数による組合せ構造の符号化
和・積・sequence・set・cycleなどの組合せ構成を係数列の演算へ翻訳し、欲しい個数を係数として抽出する。
幾何・凸最適化への変換
配置・距離・目的関数を幾何predicateや凸構造へ変換する。
幾何の基本判定・配置・座標変換
交差・方向・距離・接触条件を、外積、端点順、格子占有または変換後座標の局所判定にする。
単一サイクル成分とgraph core
連結成分の辺数と頂点数からcycle rankを判定し、必要なら葉を反復削除してcycle coreと削除順を得る。
グラフモデルと構造
対象を頂点・辺・木・有向遷移として構造化する。
静的graph等式制約のpotential伝播
可逆な加法・XOR演算で x_v=x_u⊙w と書ける辺等式をDFS/BFSで伝播し、cycle整合性を検査して各連結成分の解をroot offset一つで表す。
貪欲法と交換論
局所選択の交換または候補の支配関係から、調べる順序・残す候補・定数個のcaseを確定する。
グリッド・多次元表の局所DP
グリッド経路や多次元表の依存関係をDAG順に並べ、隣接する小さな状態集合から各セル・各添字を更新する。
群作用・軌道数え上げ
群作用の固定点を作用素のcycle typeごとに数え、BurnsideまたはPólyaで軌道数を得る。
半平面制約・凸領域の共通部分
向き付き直線の左側を線形不等式とし、平行制約を最強の境界へ集約して凸領域の包含・共通部分を扱う。
Heavy-Light Decomposition
木上pathをO(log N)本の連続区間へ分解し、配列data structure上のqueryへ変換する。
資源DPを引数で渡すHLRecDP
外部の資源DP配列を受け取って部分木の選択を反映する再帰を設計し、max-plusの子DP併合を避ける。重い子は一回だけ呼び、軽い子の重複呼出しを部分木サイズの半減により評価する。
heavy path上の多項式木DP
heavy child上の漸化式をまとめ、light subtreeのsize総和を利用して木DPの多項式合成を高速化する。
冪等演算のoverlap range query・Sparse Table
冪等な演算なら重なりを許す二つの2冪区間で任意rangeを覆えることを使い、静的queryをO(1)で答える。
暗黙・対称な完全二分木の深さ算術
巨大な完全二分木を展開せず、同じ深さの対称性と2冪で集約するか、heap番号の祖先移動と深さdの子孫label区間を使って数える。
集合上の包除原理
条件集合の交差をsubsetごとに数え、交互符号で「少なくとも一つ」「全てを避ける」対象を重複なく数える。
情報量下界・query符号設計
応答alphabetとquery回数から識別可能状態数の下界を出し、その下界に一致するcodeword割当と復号を構成する。
整数境界・同値区間分割
floor値・整数根・表記桁数・圧縮block内の式が変わる整数境界を正確に分け、区間ごとに処理する。
対話protocolとquery設計
judgeとの問い合わせ応答または交互手番をprotocolどおり実行し、query制約を守るか合法な応答手を返す。
区間合成・領域分割DP
区間・長方形の分割点を遷移にし、互いに独立な小領域の解を合成する。
isotonic regression・PAV
単調制約付き凸最小化で違反する隣接blockをpoolし、block optimumが単調になるまでmergeする。
kinetic sorting・交差event順序更新
連続parameterで隣接要素の順序が入れ替わる時刻だけをevent化し、次の有効交差を処理して全順序を更新する。
資源軸knapsack DP
容量・時間・個数などの有界資源を軸に選択の価値を更新する。
Kruskal順の閾値DSU sweep
辺とqueryを重み順に並べ、同重みの処理順を明示してDSU成分とmetadataを更新し、二点が初めて連結するminimax閾値で判定・pairing・集計を行う。
label付き連結成分分解・exponential formula
rootを含む連結成分または成分集合を一意に切り出し、全構造とconnected構造の関係をsubset DPや指数型母関数で解く。
Lagrangian relaxation・Aliens trick
個数制約へpenalty λを加えたoracleで双対下界を求める。厳密復元には個数別最適値の離散凸性などから対象個数で双対ギャップがないことを証明し、その上で個数単調性とtie-breakにより支持直線を探索する。
laminar区間族の包含木構築
互いに素または包含関係にある区間を端点順に走査し、stackで直接包含する親を定めてdummy root付き包含木を作り、点を最小包含区間へ対応させる。
遅延評価する区間作用
区間更新を要約へ作用させ、作用の合成を遅延評価する。
線形matroid交差の乱択rank判定
二つの線形matroidの表現A₁,A₂からA₁diag(r)A₂ᵀを作り、有限体上の乱択rankを共通独立集合の最大sizeとして高確率で判定する。
線形遷移・行列累乗
固定線形遷移を行列または線形漸化式として巨大回数進める。
線形方程式・rank
制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。
索引付き連結リスト
要素IDから前後linkへ直接到達し、挿入・削除で影響する局所的なlinkだけを更新する。
LIS・末尾の支配関係
同じ長さなら小さい末尾が延長可能性を支配することを示し、長さ別最小末尾を二分探索で更新してLIS・非減少部分列を求める。
lowlinkによる橋・関節点の検出
DFS木の到達時刻とlowlink値から、除去で連結性が変わる辺・頂点を特定する。
matroid greedy
独立集合族の交換公理を確認し、重み順に独立性oracleを通すgreedyが最適基底を作ることを証明する。
最大流・最小カット
選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。
meet-in-the-middle・半分全列挙
探索対象を独立に列挙できる二集合へ分け、値・mask・境界を照合して指数を半減する。
最小費用流・circulation
流量と費用を持つ残余networkを設計し、potential付き最短路・slope・cycle cancelingで流量別最小費用を求める。
一般グラフの最小重み完全matching
奇cycleを含む一般グラフで全頂点をpairにし、weighted blossomまたは重み付きTutte多項式の最小次数からperfect matchingの重みを最小化する。
Min_25・Lucy DP型の総和篩
素数和を定数個のLucy DPで求められる乗法的関数について、floor(N/i)の商集合上で素数冪を逆順に追加する簡略版Min_25でprefix sumを求める。素数冪の評価がO(1)なら、O(N^(3/4)/log N)時間・O(√N)空間。
Mo's algorithmによるオフライン区間問い合わせ
区間問い合わせを端点の移動量が小さい順に並べ、一要素の追加・削除で答えを更新する。
モデル変換
問題固有の操作を再利用可能な構造・順序・境界の問題へ変換する。
法上の四則演算・高速累乗・逆元
剰余を正規化して加減乗算し、二分累乗と逆元の存在条件を使って法上の除算・確率を計算する。
一次合同・CRT
一次合同のgcd可解性を判定し、互いに素でない法も含めて複数の剰余類を一つへ統合する。
剰余周期・指数法則
有限剰余状態の周期またはFermat/Euler型指数簡約を示し、巨大な反復やtower exponentを短縮する。
Monge・monotone minima最適化
quadrangle inequality/Monge性から各行の最適遷移位置が単調になることを示し、divide-and-conquerやSMAWKで最小値を求める。
monoid exponentiation・連結演算doubling
長さ・値・補助剰余を含む要約の結合則と単位元を定義し、巨大な反復連結を二分累乗する。
単調path contraction・DSU jump
一度確定したpath区間を次未処理pointerまたはDSU parentで飛ばし、各頂点を高々一度だけ縮約する。
単調stack・queueによる支配候補の削除
順序に走査し、新しい要素に支配された候補を二度と必要にならないことを示して一度だけ削除する。
単調境界探索
可否または値の単調性を証明し、最初・最後の成立点を探す。
乗法的位数・最小周期
合同反復の最小正周期をmultiplicative orderへ帰着し、群位数の約数を割り落として求める。
near-tree graphのkernel化
terminal外の葉除去とdegree-2 chain縮約で、cycle rankや余分な辺数だけに依存する小kernelへ答えを保って縮約する。
数論構造への変換
整数条件を合同・整除・指数・約数格子などの数論構造へ変換する。
数値半群・conductor
正の生成元の非負整数結合がconductor以後を全て覆うことを示し、巨大な到達判定を有限prefixへ縮約する。
ordered interval partition・ODT
互いに素な同値区間を左端順setで持ち、境界split・局所merge・range eraseでrun構造を動的管理する。
ordered set・multisetの動的順序管理
比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。
回文半径・Manacher
各中心の最大回文半径を左右対称性と既知区間の再利用で線形に求める。
parallel binary search・多数境界の判定共有
多数queryの未知境界をmidごとにbucketし、更新を一方向に進める判定器を各roundで共有する。
path matchingのheap縮約greedy
pathの非隣接edgeからk本を選ぶ最小重みmatchingを、最小edgeの採用と近傍二辺の補正縮約 w_l+w_r-w_i により全cardinalityについて順に求める。
永続data structure・structural sharing
変更pathだけを複製して未変更部分を共有し、各versionのrootから過去状態へアクセスする。
平面graph双対・cut/path対応
埋め込みのfaceをdual頂点へ写し、primal cutとdual path/cycleの対応から最小cut問題を最短路へ変換する。
多項式の多点評価・補間
一般点ではproduct tree・remainder tree、等比点ではchirp-z変換を使い、評価点の構造に応じて多項式を一括評価する。
factorial convolutionによる多項式Taylor shift
P(x+a) の全係数を二項展開し、階乗倍した係数列と a^i/i! の反転畳み込みへ変換して準線形時間で求める。
半順序・Dilworth・最大反鎖
比較可能性をposetとして明示し、antichain・chain cover・LDS・bipartite matching/min-cutの双対関係を選んで最適化する。
potential・weighted DSU
親へのpotential差を保ち、同一成分内の差制約と矛盾をmerge・queryできる。
累積和・差分配列
一次元区間や多次元直方体の情報、または一括加算を接頭辞・端点の差へ変換し、query・数え上げ・復元に使う。
素因数・約数分解
整数の条件を素数ごとの指数や約数格子の条件に分解する。
priority queue・best-first列挙
現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。
Prüfer code・次数制約付きlabel木
label付き木を長さN-2の列へ全単射し、頂点の出現回数=次数-1として次数条件を独立な係数条件へ変換する。
更新可能な最小十分要約
問い合わせの答えを合成でき、更新で保てる十分な統計量を導く。
乱択代数fingerprint
multiset・素因数指数vector・巨大整数式をランダムな体元やXOR和へ写し、非同値対象が衝突する確率を評価する。
乱択・Monte Carloアルゴリズム
乱数で候補またはfingerprintを選び、成功条件と誤り確率を評価して反復や事後検証を設計する。
区間monoid要約
queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。
連分数・Stern–Brocot有理近似
Euclidの商列またはStern–Brocot区間を辿り、分母制約下の最良有理近似を求める。
再帰・圧縮・入れ子文字列の走査
明示展開できない反復・再帰文字列をblockで追跡するか、対応括弧で入れ子区間を飛び越えて作用を合成する。
再帰分割・分割統治
pivot・bit・時刻区間・積木で部分問題へ再帰分割し、部分結果を重複なく合成する。
鏡像法・reflection principle
境界を初めて破るpathを鏡像pathへ写す符号付き全単射により、壁付きwalkを無境界または巡回畳み込みへ変換する。
Relaxed・online convolution
係数が順に確定する因果的畳み込みをblock分割し、確定済みblock間だけをNTTでまとめて更新する。
rerooting・全方位木DP
辺の両側情報とprefix/suffix合成を用いて、全ての根に対する木DP値を線形または準線形時間で得る。
逆向きのオフライン処理
時間依存を逆走査・逆操作・last-write時刻で単調または静的な処理へ変換し、元の時点の答えを復元する。
rollback・DFS入退場の状態復元
更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。
根付き木DP・部分木集約
子部分木の状態をbottom-upに合成し、親へ渡す最小十分なopen/closed状態や要約を設計する。
Robinson–Schensted対応・Young tableau
順列をYoung図形と二つの標準盤へ全単射し、LIS/LDS制約をshape制約とideal DPへ変換する。
run-length状態の動的遷移
同値な連続要素をrunへ圧縮し、局所操作で変わるrunのsplit/mergeと長さだけを更新する。
SCC・縮約DAG・トポロジカル順序
強連結成分を一頂点へ縮約し、閉路を除いたDAG上の順序・DP・coverへ変換する。
Segment Tree Beats
nodeの最大/次点/個数等からrange chmin/chmaxが一括適用できる条件を判定し、失敗時だけ子へ降りる。
Segment Treeのcanonical区間分解
区間をO(log N)個のcanonical nodeへ分解してrange object・生存時間・range edgeを配置し、point queryでは対応するroot-to-leaf pathから該当objectを集める。
半環行列・min-plus/max-min遷移
遷移の結合と候補選択を半環の積・和として行列化し、結合則を使って固定長walkを二分累乗または区間積で処理する。
分離凸・凹の単調限界値選択
各対象の限界費用が単調増加(または限界利益が単調減少)することを使い、複数の限界値列から必要な上位・下位K項をpriority queue mergeまたは値の閾値計数で選ぶ。
分離可能線形変換・Walsh–Hadamard変換
Kronecker積型の多次元変換を各軸の小変換へ分離し、XOR convolution等をpointwise積へ移す。
列・文字列のrolling fingerprint
順序を保つprefix hashと連結則を設計し、部分列のhash差やLCP二分探索で列の一致を比較する。
列・subsequence DP
列のprefixや最後に選んだ要素を状態にし、順序を保つ選択を組み立てる。
最短路を証明する木・経路の復元
最短距離の等式を満たす辺から、親・木・実現経路を選ぶ。
最短路モデル
重み付きグラフの距離を計算し、距離の確定条件や最短路木の枝構造から経路・閉路の最適化を行う。
slope trick
区分線形凸関数を左右breakpointのheapと定数項で表し、|x-a|追加・平行移動・prefix minimumを更新する。
small-to-large・DSU on Tree
小さいcontainerを大きいcontainerへ併合する。要素を保持する場合は所属サイズの倍増、重複を消すsetでは生存要素のサイズ増大と消滅要素への課金、分割では小さい側の半減を用いて総仕事量を証明する。
最小・最大全域木とcut・cycle性質
辺重み順の成分併合をcut・cycle性質で正当化し、全域木の構成と閾値別成分数による最適重みを導く。
状態グラフのモデリングと探索
暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。
状態・配置の正規化
対称操作で同値な状態を一意な標準形へ写し、重複した探索・数え上げを除く。
静的sorted range index・Merge Sort Tree
各canonical区間へsorted列とprefix aggregateを構築し、値域境界付きのrange count/sumを二分探索で答える。
Static Top Treeによる動的木DP
境界頂点つきtree clusterをrake・compressで二分合成し、局所更新後の木DP値を根まで再計算する。
Steiner tree subset DP
terminal subsetと終点を状態に、subset分割mergeとmulti-source shortest path relaxationを交互に行う。
Stern–Brocot木の経路と祖先
隣接分数の行列式が1であることを保ち、mediantとEuclidの商列からStern–Brocot木の経路を同方向の連続回数へ圧縮する。経路の共通prefixで祖先関係と必要な祖先集合を求める。
Stirling変換と階乗基底変換
冪基底と下降階乗基底の係数をStirling数で相互変換し、rank別の計数列を目的の基底へ移す。
確率・期待値DP
確率遷移に対する期待値・分布・到達確率の再帰式を解く。
文字列周期・primitive word
prefix一致またはborderから最小periodを求め、文字列をprimitive rootと反復回数へ正規化する。
文字列状態表現
一致・接辞・反復を十分な文字列状態へ圧縮する。
部分集合・bitmask状態DP
各bitの意味を固定し、訪問集合・選択集合・frontierなどの部分集合状態間を遷移する。
subset convolution
互いに素な部分集合分割に沿う畳み込みをrank別zeta変換などで高速に計算する。
subset zeta・Möbius変換
Boolean lattice上のsubset/superset和とexact値をzeta変換・Möbius反転で相互変換する。
Suffix Automaton
endpos同値類をstateとし、suffix linkとcloneで全部分文字列の遷移を線形状態数へ圧縮する。
接尾辞順序・LCP索引
全接尾辞の辞書順とLCPを索引化し、部分文字列の順序・出現範囲・順位・distinct数を求める。
SWAG・two-stack queue aggregation
queueを二つのstackへ分け、それぞれの向きにmonoid積を持ってpush/pop/foldを償却O(1)で処理する。
平方根・閾値による軽重分類
頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。
推移閉包
各始点探索またはWarshallの段階不変条件により全頂点対の到達関係を計算する。
ancestor query・LCA
根付き木の祖先関係を時刻またはbinary liftingで索引化し、LCAと木上距離を答える。
木の均衡分離点と重心分解
非負重みの各成分を半分以下にする一点を選ぶ。頂点数を重みとし各成分で繰り返すと、対数深さの重心分解を得る。
木距離の剰余類による構造分類
木の一つの基準点から各頂点への距離を求め、距離の剰余類と局所構造から頂点の役割や周期的な部品構造を分類する。
Euler順による部分木区間化
DFS入退時刻で各部分木を連続区間へ写し、配列上の更新・集約へ変換する。
木距離・直径・中心・最遠点
木の一意経路距離を少数の基準点から一括計算し、距離label・直径端点・中心・最遠点性質で頂点集合の距離条件を整理する。
木モデルと構造
木固有の根・部分木・path・separator構造へ問題を写し、利用する性質を選ぶ。
01 on Tree・親先行順序のcluster縮約
親が子より先という順序制約の下でclusterの交換比較量を導き、priority queueとDSUで最良clusterを親へ縮約する。
Trieによる共有接頭辞の索引
文字列集合の各文字遷移を木として共有し、prefix通過数・prefix DP・辞書順探索をnode上で処理する。
尺取り法・sliding window
一列の連続窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進める。
2-SAT・含意グラフ
二値選択のclauseを含意辺へ変換し、literalと否定literalのSCC関係から可解性と代入を得る。
二変数の凸区分線形格子最適化
二つの整数parameter上の凸区分線形目的について、折れ目直線の交点から連続最小候補を作り、定数半径内に整数最適解があることを証明して有限格子点へ縮約する。
値軸のbucket分割と区間集約
値軸を長さBのblockに分け、完全blockの要約と端数の走査を合成する。点更新とqueryの回数を別々に数え、O(1)更新とO(V/B+B)の値prefix取得を選ぶ。
値域集約による部分列DP
末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。
virtual tree・auxiliary tree
選択頂点と隣接LCAだけをEuler順にstack接続し、必要な祖先関係を保つ小木を構築する。
重み付き二部完全matching
assignment matrixのdual potentialとtight edgeを保ち、Hungarian法または同値なmin-cost flowで完全matchingの重みを最適化する。
基準解による変更影響の局所化
変更前の解・実行列をwitnessとし、それを壊さない変更では答えが変わらないと示して再計算対象を絞る。
XOR線形基底
整数をF2 vectorとして最高bit pivotで消去し、独立性判定・最大XOR・表現可能性をonlineに保つ。
XOR閾値matchingのbit分割再帰
固定閾値xに対し、XORがx以上となる最大pair数を求める。最上位bitで集合を分け、閾値bitが0なら確定できるcross pairを最大化し、1ならcross pairだけを残し、同一集合内と二集合間の再帰値を合成する。
Z algorithmによるprefix matching
各位置からprefixと一致する最大長を既知のZ-boxから再利用し、全位置の一致長を線形時間で求める。