このページでは、通常は「アルゴリズム」とは呼ばれないようなものたちを紹介する。通常のアルゴリズムたちについては Kyopro Encyclopedia of Algorithms を参照のこと。
- 45 度回転
- 45 度回転とは、入力として与えられた $2$ 次元平面の点 $(x, y)$ を $(x-y, x+y)$ や $(x+y, x-y)$ に変換してから扱うこと。
- bit DP
- bit DP とは、状態として集合を用いる DP であって、特にその集合を bitset として扱うもののこと。状態の持ちかたによる DP の分類のひとつ。
- in-place DP
- in-place DP とは、セグメント木や convex hull trick を用いて DP を高速化すること。。DP の高速化手法のひとつ。あるいは、実装方法に基づく DP の分類のひとつ。
- イベントソート
- イベントソートとは、クエリを時刻順にソートして順番に処理するテクニックのこと。
- ヘビ
- 平面上の構築問題ではなにかをヘビ状に配置するとうまくいくことが多い。
- 二乗の木 DP
- 二乗の木 DP とは、計算量が一見 \(O(N^3)\) に見えるが実は \(O(N^2)\) であるようなある種類の木 DP のこと。実装方法と計算量による DP の分類のひとつ。
- 列を最小値で分割して再帰する (名称募集中)
- 列に対する値を求めたいとき、列をその最小値で分割して再帰的に計算するとうまくいくことがある。
- 区間から始切片への帰着 (名称募集中)
- 「区間 $\lbrack l, r)$ に含まれる整数 $x \in \lbrack l, r)$ であって条件 $\varphi(x)$ を満たすものの個数を求めよ」という問題は「$n$ 未満の自然数 $x \in n$ であって条件 $\varphi(x)$ を満たすものの個数を求めよ」という問題に帰着するとよい。微分積分学の基本定理を思い出すとよい。
- 変数分離
- 変数分離とは一般には微分方程式を解くための手法であるが、競技プログラミングにおいても類似の手法を用いることが多く見られる。
- 戻す DP
- 戻す DP とは、DP の遷移の逆演算を用いる DP のこと。DP の高速化手法のひとつ。あるいは、実装方法に基づいた DP の分類のひとつ。
- 拡張グラフ
- 拡張グラフとは、もともと与えられたグラフを何らかの方法で拡張したグラフのこと。もともとの頂点の集合 $V$ と時刻の集合 $\lbrace 0, 1, \dots, T - 1 \rbrace$ の直積 $V' = V \times \lbrace 0, 1, \dots, T - 1 \rbrace$ を新しいグラフの頂点集合とすることが多い。たいてい Dijkstra 法と共に用いられることが多い。
- 桁 DP
- 桁 DP とは、自然数の \(10\) 進数展開などを桁ごとに決定していくような DP のこと。状態の持ちかたによる DP の分類のひとつ。
- 端点を共有する区間をつないでできるグラフの連結成分 (名称募集中)
- 端点を共有する区間の間に辺を張って、区間を頂点とするグラフを作ると、これはよい性質を持つことがある。
- 答えの二分探索
- 二分探索を用いると「得られる点数の最大値を求める」という最大化問題を「ある点数を得ることは可能か求める」という判定問題に帰着させられる。
- 箱根駅伝 DP
- 区間の集合を構成するような DP であって「左端は決まったが右端はまだ決まってない区間の数」と「右端は決まったが左端はまだ決まってない区間の数」を状態とする DP のこと。
- 行や列に対応する頂点を作る (名称募集中)
- 大きさ $H \times W$ のマス目の上のなにかの連結性を考えるなどの場合に、行と列のそれぞれに対応する $H + W$ 個の追加の頂点を考えるとうまくいくことがある。
- 補集合を数える
- 補集合を数えるとは、ある条件を満たす要素の個数を求めることを、ある条件を満たさない要素の個数を求めることによって行うテクニックのこと。
- 逆から考える
- なにかを順番に処理するとき、逆から処理するとうまくいくことがある。union-find 木などのような、追加はできるが削除はできない構造を使う場合に多い。
- 重ね合わせに分解する (名称募集中)
- $H \times W$ の行列 $A$ を適切に 構成したいとき、長さ $H$ のベクトル $b$ と長さ $W$ のベクトル $c$ を作り、行列 $A$ を $A _ {y, x} = f(b_y, c_x)$ (あるいは $A = b c^T$) として生成するとうまくいくことがある。