P6880 JOI 2020 Final オリンピックバス
有向グラフが与えられる。辺を通るコスト \(C_i\)、1本の辺を反転させるコストを \(D_i\) とする。頂点 \(1\) から \(n\) へ、さらに \(n\) から \(1\) へ移動するとき、辺の反転を高々1回まで許したときの最小コスト和を求めよ。
全ての辺に対して反転を試すのは非効率なので、影響を解析する。\(f(s,t)\) を元のグラフでの \(s\) から \(t\) への最短距離とする。辺 \((u,v)\) を反転した後の \(1\) から \(n\)、\(n\) から \(1\) への最短距離をそれぞれ \(D1, D2\) とすると、
D1 = min(f(1, n), f(1, v) + w + f(u, n))
D2 = min(f(n, 1), f(n, v) + w + f(u, 1))
ここで重要な性質：グラフ \(G\) において、根 \(x\) からの最短経路木 \(T\) を構築する。\(T\) に含まれない辺を1本削除しても、\(x\) から他の任意の頂点への距離は変化しない。
この性質により、最短経路木に含まれない辺については、反転後の \(1, n\) からその両端点への最短距離は変わらないため、再計算は不要となる。最短経路木に含まれる辺は最大で \(n-1\) 本なので、それらの辺に対してのみ再計算を行えばよい。
グラフが密な場合は、優先度付きキューを用いないダイクストラ法が適している。多重辺がある場合は辺の番号で識別する。始点が \(1\) や \(n\) でない最短距離を求めるときは、逆グラフ上で \(1\) または \(n\) を始点としたダイクストラ法を用いる。
ABC264Ex Perfect Binary Tree
動的に頂点が追加される木において、頂点 \(1\) を根とする完全二分木（full binary tree）の個数を求めよ。
DPを考える。完全二分木の高さは最大で \(\log n\) なので、高さが \(\log n\) 未満の頂点のみを考慮すればよい。
\(dp_{x, dep}\) を、\(x\) を根とし、最大深さが \(dep\) である完全二分木の個数と定義する。単純な遷移は、深さ \(dep-1\) の2つの完全二分木を組み合わせることである：
dp[x][dep] = Σ (u < v, u, v ∈ son_x) dp[u][dep-1] * dp[v][dep-1]
動的な頂点追加に対してこの遷移を毎回計算するのは重い。そこで、2乗の公式を用いて式を変形する：
dp[x][dep] = (1/2) * ( (Σ_{u ∈ son_x} dp[u][dep-1])^2 - Σ_{v ∈ son_x} (dp[v][dep-1])^2 )
これにより、和と2乗和をそれぞれ管理することで、1回の頂点追加あたり \(O(1)\) で遷移を更新できる。全体の計算量は \(O(n \log n)\) となる。
CF452F Permutation
長さ \(n\) の順列が与えられる。この順列の部分列（連続でなくても良い）に、等差数列をなす3要素が存在するかを判定せよ。
正攻法はセグメント木とハッシュを用いることだが、次の性質を利用できる：等差数列をなす3要素が存在するならば、その中央の要素と両端の要素との距離は高々 \(12\) である。この値は \(n\) に依存するが、厳密な証明は難しい。この性質を用いれば、効率的な判定が可能となる。
ABC329F Colored Ball
各箱にボールの集合がある。クエリとして箱のマージが与えられる。各クエリの後、各箱のボールの色の種類数を出力せよ。
各箱を set で管理し、マージの際には要素数が小さい方の set を大きい方にマージする、いわゆるデータ構造をマージする一般的なテクニック（DSU on tree / union by size）を用いる。これにより、効率的に処理できる。
CF1898D Absolute Beauty
\((a_i, b_i)\) を区間とみなすことを考える。1回の操作で増加させられる長さを最大化するには、最も大きな左端 \(l_i\) と最も小さな右端 \(r_j\) を選んで操作すればよい。
テクニック： \(|a_i - b_i|\) のような式は、区間として捉え直すことで、場合分けが容易になる。
P8386 & P10375
長さ \(n\) の数列であって、以下の条件を満たすものの個数を \(10^9+7\) で割った余りを求めよ：
- 各要素は \([1, m]\) の整数である。
- 数列に対して、「長さが2以上で、両端の値が等しい区間を削除する」操作を繰り返すことで、数列全体を空にできる。
DPを考える。この手の数え上げでは、末尾に1要素を追加する場合を考えると良い。ある列 \(S\) が条件を満たすとき、それに任意の要素 \(x\) を連結した \(S+x\) もまた条件を満たす（理由は自明）。
状態を \(dp[i][j][0/1]\) で定義する：\(i\) 要素まで埋めた列が、条件を満たす/満たさない、そして \(i+1\) 番目に挿入される要素が既出の \(j\) 種類の値のいずれかである場合の数。
テーブルを埋める方向で遷移を考えると次のようになる：
(dp[i+1][j][1] += dp[i][j][0] * j) %= mod;
(dp[i+1][j][0] += dp[i][j][0] * (m - j)) %= mod;
(dp[i+1][j][1] += dp[i][j][1] * j) %= mod;
(dp[i+1][j+1][0] += dp[i][j][1] * (m - j)) %= mod;
P11013 「ALFR Round 4」C 粉碎
最適な戦略は、ある接頭辞を削除し、残りはすべて単一のカードとして残すことである。したがって、最後に削除できるカードを見つければよい。そのカードは必ずペアになるカードである。
\(dp[i]\) を区間 \([1, i-1]\) を完全に削除できるかどうかを示すブール値とする。\(dp[las[i]]\) が真であれば、\([1, i]\) を削除可能である。ここで \(las[i]\) は \(a_i\) が最後に現れた位置とする。遷移を考えると、\(las_i\) が削除されるための条件は、\(las_{las_i}\) とペアになるか、ある区間 \((las_i, i)\) 内のある \(j\) の \(las_j\) とペアになることである。これをまとめると、\(dp_i\) は \(dp_{las_j}, j \in [las_i, i)\) の論理和となる。
これは \(O(n)\) にはならないため、累積和を用いて高速化する。\(sum_i = sum_{i-1} + dp_{las_i}\) と定義すると、遷移は \(dp_i = [sum_{las_i-1} < sum_{i-1}]\) となる。
P2446 SDOI2010 大陸争覇
ある頂点 \(u\) のアンロック時間は、「前置ノードの最大アンロック時間 \(D\)」と「自身への到着時間（アンロックを考慮しない）」のうち、大きい方となる。
しかし、単純にダイクストラ法を実行してからトポロジカル順に更新するだけでは不十分である。理由は、ダイクストラ法で求めた最短経路上の頂点がまだアンロックされていない可能性があるからである。そのため、ダイクストラ法の実行と同時に、トポロジカル順序でアンロック時間を更新する必要がある。このとき、アンロック時間を記録するための別の配列を用意すること。
UVA11987
素集合データ構造（Union-Find）をそのまま用いると誤った結果を生じる。回避策として、各集合に対してダミーノード（仮想的な根）を作成する。要素をマージする際には、マージしたい要素を対応する集合のダミーノードに接続する。ダミーノードは移動しない。これにより、正しく処理できる。
P1525 [NOIP2010 提高组] 関押罪犯
重み付きUnion-Findを用いる。2つのノード間の関係（同じグループか異なるグループか）は、各ノードから根までの重みの差の偶奇で判定する。
P6061 加油武汉 疫情調査
（注：問題文が不完全なため、解答不能）
P11022
グラフが非連結または木である場合は解なし。非木辺を追加して閉路を形成することを考える。単純な方法として、ある1頂点を白、他のすべての頂点を黒に塗る方法があるが、これは反例により破綻する。問題の条件を満たすためには、ある辺 \((u,v)\) を含む閉路の一部の頂点を白に塗る必要がある場合がある。
P8817 CSP-S 2022 假期計画
前処理として \(O(n^2)\) で全点対間最短距離をBFSにより求める。素朴な方法として、訪れる4つの地点を全て列挙するのは非効率なので、中間の2地点 \(B, C\) を全探索することを考える。\(A, D\) は、それぞれ頂点1からの距離制限 \(k\) を満たす必要がある。各 \(B\)（または \(C\)）について、条件を満たす最良の \(A\)（または \(D\)）をいくつか保持しておけばよい。選択する頂点が重複しないように、各 \(B\)（または \(C\)）に対して少なくとも上位3つ程度の候補を set や優先度付きキューで管理する。\(k\) は1加算すること、および long long 型を使用することに注意。
P3537 POI2012 SZA-Cloakroom
クエリをオフラインで処理する。クエリを \(m\) の昇順に、アイテムを \(a\) の昇順にソートする。残りの2つの制約を扱うために、状態を \(dp[i]\) を「アイテムの \(c\) の和が \(i\) となるような選択方法の中で、\(b\) の最小値の最大値」と定義する。この値が \(m + s\) より大きければ、その選択は有効であると判定できる。
P8868 NOIP2022 試合
素朴な分割統治法では \(O(q n \log n)\) で52点が得られる。クエリをオフラインにし、分割統治の過程で各区間の寄与を、それを含むクエリに加算することで高速化できる。
P4155 SCOI2015 国旗計画
各人に対して、その人に含まれる左端点の中で、最も右側に端点を持つ人を貪欲に選択できる。環状の構造を扱うために、列を2倍に引き伸ばし（破線環状）、ダブリングを用いて区間被覆を高速に求める。
ABC346G
ある数字 \(x\) が寄与する区間は、\(x\) が1度だけ現れる区間である。この区間は、\(x\) の出現位置 \(i\) とその直前の出現位置 \(l_i\)、直後の出現位置 \(r_i\) を用いて、\([l_i+1, i]\) から \([i, r_i-1]\) までの範囲となる。この寄与を図形的に解釈すると、左下 \((l_i, i)\)、右上 \((i, r_i)\) の長方形の面積の和を求める問題に帰着できる。これは、平面走査（スイープライン）を用いて解くことができる。
P9991 Ynoi Easy Round 2023 TEST_107
情報がスイープライン（平面走査）に適している。クエリをオフラインにし、右端点でソートする。
極大な部分区間は以下の3パターンに分類される：
- 左端が \(l\) と一致する場合：\(l' = l, r' = i\) で、\(a_{i+1}=x\) かつ \([l, i]\) に \(x\) 以外の値のみが存在する。
- 右端が \(r\) と一致する場合：\(l' = i, r' = r\) で、\(a_{i-1}=x\) かつ \([i, r]\) に \(x\) 以外の値のみが存在する。
- 左右両端が \(l, r\) と異なる場合：\(a_{l'-1}=a_{r'+1}=x\) かつ \([l', r']\) に \(x\) 以外の値のみが存在する。
各パターンに対して、スイープラインで処理する。
パターン1では、\(las[i]\)（\(a_i\) が最後に現れた位置）を記録しておき、スイープラインで \(i\) を処理するたびに、セグメント木上の \(las[i]\) の位置を \(i\) に更新する。クエリの右端点が \(i\) のとき、セグメント木の区間 \([0, l_j-1]\) の最大値が、条件を満たす \(i\) の位置となる。
パターン2は、配列とクエリを反転させて同様に処理する。
パターン3では、\(las[i]\) の位置を \((i-1) - (las[i]+1) + 1\) に更新し、クエリでは区間 \([l_j, r_j]\) の最大値を直接取得する。
スイープラインは以下のように実装する：
for (int i = 1, j = 1; i <= n; ++i) {
update(1, 0, n, las[i], i); // las[i] は0になる可能性があるため
while (j <= m && queries[j].r == i) {
ans[queries[j].id] = max(ans[queries[j].id], query(1, 0, n, 0, queries[j].l - 1) - queries[j].l);
++j;
}
}
GSS2 - Can you answer these queries II
セグメント木の葉ノードが、その位置を開始点とする最大部分和を表すように設計する。スイープラインを用いて、区間 \([las_i+1, i]\) に \(a_i\) を加算する。これにより、同じ値の寄与が重複しないようにしつつ、履歴上の最大値を管理する。履歴最大値を管理するためには、履歴最大値を更新するためのタグ（lazy tag）も同時に管理する必要がある。
P9990 Ynoi Easy Round 2023 TEST_90
全ての部分区間の個数を数える必要がある。スイープラインを用いて、セグメント木上の履歴バージョンの和を記録する。各値の寄与は、前問と同様に区間 \([las_i+1, i]\) であり、これは各区間のパリティ（偶奇）を反転させる効果を持つ。
セグメント木の各ノードにおいて、そのノードが担当する区間内の部分区間のうち、答えが \(0\) または \(1\) となるものの個数をそれぞれ \(t0, t1\) として保持する。各ノードの答えは、\(t0, t1\) と対応するタグの積の和として計算される。
P5290 [十二省連合試験 2019] 春節十二響
鎖状の部分問題は、この問題の本質を捉えている。根 \(1\) からは高々2本の枝が出ているので、それらの枝の頂点の重みをリストアップしてソートし、ランキングが同じもの同士をペアにする。各ペアの大きい方の値が、最終的な答えに加算される。
一般の木に対しては、各頂点に最大ヒープを持たせ、子のヒープを親のヒープにマージする（小さい方を大きい方にマージするテクニックを用いる）。複雑度はポリログ程度となる。
P6626 [省選連合試験 2020 B 巻] 消息伝達
頂点 \(u\) から距離 \(k\) にある頂点の個数を求めるクエリを処理する。
重心分解（Centroid Decomposition）を用いる。クエリをオフラインで各頂点に紐付けておく。現在の重心 \(u\) について、その部分木内の各深さにある頂点の個数を記録する。頂点 \(u\) に関するクエリの答えは \(cnt[k - depth[u]]\) で与えられる。子 \(v\) の部分木に入る前に \(cnt\) を更新し（子の部分木の深さは1小さいため）、出た後に元に戻す。
void dfs_upd(ll u, ll fa, ll k) {
cnt[depth[u]] += k; // k = 1 or -1
for (int v : g[u]) {
if (v == fa || vis[v]) continue;
dfs_upd(v, u, k);
}
}
P8600 [蓝橋杯 2013 省 B] 連号区間数
区間 \([l, r]\) が条件を満たすための必要十分条件は、\(\max_{l \le i \le r} a_i - \min_{l \le i \le r} a_i + l = r\) である。この式を変形すると、\(\max - \min + l \ge r\) が常に成り立つことがわかる。したがって、左辺の最小値を達成する区間の個数が答えとなる。
P4656 [CEOI2017] Palindromic Partitions
文字列の両端から走査し、同じ部分文字列が現れたら、それを1つのパーティションとして切り出す。この貪欲戦略が最適であることが証明できる。
P5070 [Ynoi2015] 即便是看不到未来
（注：問題文が不完全なため、解答不能）
CF522D
スイープラインの典型的な問題。\(las[i]\) の位置を \(i - las[i]\) に更新し、区間最小値を求める。
P1648 看守
マンハッタン距離の式を変形する。絶対値の性質 \(|a_i - b_i| = \max(a_i - b_i, b_i - a_i)\) と、\(\max\) の分配法則を用いると、
Σ |a_i - b_i| = max_{q_i∈{-1,1}} ( Σ q_i * a_i + Σ -q_i * b_i )
となる。ここで \(q_i\) は各次元の符号を表す。複数の点の間の最大距離は、各点について \(\sum q_i * x_i\) を計算し、その最大値と最小値の差を取ることで求まる。符号の組み合わせは \(2^d\) 通りであり、\(d\) は次元数である。
P9743 「KDOI-06-J」旅行
多次元DPが基本となる。状態を \(dp[x][y][k][ka][kb]\) と定義する：\((x, y)\) にいて、\(k\) 円使い、横方向のチケットが \(ka\) 枚、縦方向のチケットが \(kb\) 枚残っている場合の数。遷移では、\((x, y)\) で購入するチケットの枚数を考慮する。このDPは \(O(n^7)\) となるが、後ろ2次元について2次元累積和を用いることで \(O(n^5)\) に改善でき、さらに次元を1つ減らすために転置（rolling array）を用いる。
P1896 [SCOI2005] 互不侵犯
状態を \(dp[i][j][k]\) と定義する：\(i\) 行目の状態が \(k\) であり、\(i\) 行目までに \(j\) 個の王を配置した場合の数。あらかじめ可能な状態（王が隣接しない配置）を列挙し、状態間の遷移可能性を判定してDPを実行する。
QOJ8831 Chemistry Class
結論：マッチングの線分が交差することはなく、また2段以上の入れ子構造は存在しない。したがって、ペアはある区間 \([l, r]\) で \(l\) と \(r\) がペアになり、内部は隣接する要素同士がペアになる形で構成される。DP \(dp[i]\) を「最初の \(i\) 個（\(i\) は偶数）の最大値」と定義し、線分木やスライド最小値（monotone queue）を用いて遷移を高速化する。
P11081 [ROI 2019 Day 1] 自動運転
各点の積雪の深さが \(k\) 以下かどうかは、その点が除雪された時刻が現在時刻 \(t\) から \(k\) を引いた値以上かどうかと同値である。経路は高々2回しか折れ曲がらないという性質がある。各行・列に対して、タイムスタンプの最大値・最小値およびその位置を管理する線分木を2つ用意する。
P6370 [COCI2006-2007#6] KAMEN
各列に対して、X または O が存在する位置を set で管理する。ボールの落下をシミュレートする際に、lower_bound を用いて次の障害物の位置を求める。ただし、これだけでは最悪ケースで \(O(nr \log r)\) となる。列数が少ないことを利用して、各列についてドロップ開始位置から各段における最終的な列番号を事前計算しておくことで高速化できる。
P3052 [USACO12MAR] Cows in a Skyscraper G
ビットDPを用いる。状態 \(dp[j]\) を「選択済みのアイテムの集合 \(j\) で、最後のグループの総重量」と定義する。各グループにはアイテムを詰められるだけ詰める（貪欲に詰めるわけではなく、全ての組み合わせを試す）。遷移は、未選択のアイテムを現在のグループに追加可能かを判定する。
P4568 [JLOI2011] 飛行路線
層別グラフ（階層化グラフ）の典型問題。\(k+1\) 層のグラフを作成し、各層は元のグラフと同一である。\(i\) 層目は \(i\) 回の無料航空券を使用した状態に対応する。元の辺に加えて、\(i\) 層目の \(u\) から \(i+1\) 層目の \(v\) へ、重み0の辺を張る。その後、ダイクストラ法で最短経路を求める。
P9751 [CSP-J 2023] 旅遊巴士
2つの制約がある：パスの長さが \(k\) の倍数であること、および各辺の開放時刻。長さの制約に対しては、\(O(nk)\) の層別グラフが利用できる。各層は距離を \(k\) で割った余りに対応する。開放時刻の制約は、ダイクストラ法の実行中に、ある頂点に「待つ」ことで対応できる。もし現在時刻よりも開放時刻が後であれば、その差だけ待てばよい。
P11188 「KDOI-10」商店砍価
set に対して lower_bound/upper_bound を使用する際は、s.lower_bound(x) の形式で呼び出すこと。そうしないと計算量が悪化する。
P4571 [JSOI2009] 瓶子和燃料
ベズーの定理（拡張ユークリッドの互除法）により、容量 \(a, b\) の瓶で得られる燃料の量は \(\gcd(a, b)\) の倍数となる。したがって、問題は「\(k\) 個の瓶を選び、それらの容量の最大公約数を最大化する」ことに帰着される。各数の約数を列挙し、最も多くの数に現れる約数を見つければよい。
P3792 由乃與大母神原型和偶像崇拝
区間が連続する整数列である条件は、\(\max - \min = r - l\) であり、かつ（平方和などの）その区間の総和が、\(\min\) から \(\max\) までの整数の総和と一致することである。平方和は、\(\frac{n(n+1)(2n+1)}{6}\) で計算でき、オーバーフローを避けるために __int128 を使用する。
P3435 [POI2006] OKR-Periods of Words
接頭辞 \(S[1:i]\) が周期であるための条件は、\(S[i+1:n]\) が \(S[1:i]\) の接頭辞かつ \(S\) の接尾辞（すなわち border）であることである。したがって、各接頭辞の最短の border を求め、その長さを全体の長さから引いた値が答えとなる。KMPアルゴリズムを用いて border を求め、パス圧縮を用いて高速化する。
P2375 [NOI2014] 動物園
各接頭辞について、長さがその半分以下である border の個数を求める。KMP で border を求め、それらの border のうち条件を満たすものを数えるための DP を行う。
Drink Bar
（シミュレーションコンテストの問題）3つの属性を持つ要素からなる集合を考える。任意の部分集合 \(S\)（\(|S| \le 3\)）について、特定の条件を満たすものの個数を数え上げる。包除原理を用いて数え上げる。\(|S|=1\) は自明、\(|S|=2\) は3次元偏序問題（CDQ分割統治）、\(|S|=3\) はさらに複雑な包除原理を用いる。
P3065 [USACO12DEC] First! G
トライ木を構築する。文字列が辞書順最小となりえない条件は、(1) 自身が他の文字列の接頭辞である、(2) 同じノードから分岐する際に、異なる文字間に矛盾が生じる（順序関係のサイクルが生じる）場合である。矛盾はグラフで表現し、トポロジカルソートで検出する。
[ABC134F] Permutation Oddness
順列 \(p\) とインデックス \(i\) のマッチングと考える。ボール（\(p_i\)）を左、箱（\(i\)）を右に配置し、水平線とマッチング線を引くと、交差の数が「奇妙さ」となる。DP 状態を \(dp[i][j][k]\) と定義する：最初の \(i\) 個のボールと箱を考慮し、\(j\) 個の未マッチのボール/箱が存在し、現在の奇妙さが \(k\) である場合の数。遷移は3つの場合がある：\(i\) のボールと箱の両方をマッチさせる、片方だけをマッチさせる（既存の未マッチ要素と）、どちらもマッチさせない。
P4302 [SCOI2003] 文字列折畳み
区間DPを用いる。状態 \(dp[l][r]\) を区間 \([l, r]\) を折り畳んだ際の最短長さとする。遷移は、区間を2つに分割するか、区間が繰り返しパターン（循環節）を持つ場合に折り畳む。循環節の判定にはロリハ（Rolling Hash）を用いる。
P3698 [CQOI2017] 小Qの碁盤
木の最深ノードまでの深さを \(mx\) とする。\(k \le mx\) の場合、答えは \(k+1\) となる（根を含む）。\(k > mx\) の場合、\(k - mx\) の余剰ステップを利用して、新たなノードを訪れては最深経路に戻ることを繰り返す。2ステップで1つの新しいノードを訪れられるので、答えは \(\min(n, mx + 1 + (k - mx) / 2)\) となる。
CF1613D MEX Sequences
合法な MEX 列は2つのタイプに分類される：(1) 値が単調非減少で、隣接する値の差が0か1である、(2) 前半はタイプ1で、後半は \(x-1\) と \(x+1\) のみからなる（ただし \(x\) は前半の最後のMEX）。DP は \(dp[x][0/1]\) を「最後の要素の MEX が \(x\) であるタイプ1/2の列の個数」と定義する。
P8860 動態図形連結性
オフラインで処理する。各辺が最初に削除される時刻 \(d_i\) を定義し、削除されない辺は \(d_i = q + 1\) とする。全ての削除操作が完了した後、最後に残る唯一のパスを求める。このパス上の辺の \(d_i\) の列は、辞書式順序で最大となる。この性質を利用し、ダイクストラ法の変形（各ステップで \(d_i\) が最大の辺を選択する）によって、最後のパスを求める。
P2466 [SDOI2008] Sue 的小球
区間DP。「ある区間の卵を全て回収し終えた時、人はその区間の左端または右端にいる」という状態を考える。\(dp[l][r][0/1]\) を「区間 \([l, r]\) の卵を回収し、左端(0)または右端(1)にいるときの最大スコア」と定義する。スコア計算の際、時間経過による減少スコア（卵が落下する）をあらかじめ見込んでおくテクニックを用いる。
P1220 街路灯を消す
上記の問題と同様の区間DPである。
P4870 [BalticOI 2009 Day1] 甲虫
水滴を全て飲む必要はなく、価値が負になる場合は飲むのをやめる。したがって、飲む水滴の個数を固定してDPを行う。
[ABC219H] Candles
上記の問題の一般化であり、アイテムの初期価値が異なる場合。状態に「この区間の外からさらにいくつアイテムを選ぶか」という情報 \(k\) を追加し、\(dp[l][r][k][0/1]\) とする。
[AGC034D] Manhattan Max Matching
マンハッタン距離の絶対値を、符号の組み合わせを用いて線形な式で表現するテクニックを用いる。4つの中継ノードを導入し、左側の点から中継ノードへ、中継ノードから右側の点へ、重み付きの辺を張る。最大コストフロー問題として解く。
P5658 [CSP-S2019] 括弧樹
スタックを用いて、各ノードにおける正しい括弧列の個数を管理する。新たに追加された括弧がマッチした場合、そのマッチによって新たに形成される正しい括弧列の個数を計算する。
[AGC014D] Black and White Tree
先手必勝の条件は、ある頂点が奇数サイズの部分木を少なくとも2つ持つことである。そうでなければ、木は完全マッチングを持ち、後手必勝となる。
[ARC168D] Maximize Update
\(dp[l][r]\) を区間 \([l, r]\) 内の操作のみを使用して最大何回塗れるかと定義する。前処理として \(f[l][r][i]\) を「区間 \([l, r]\) 内の操作で \(i\) を塗れるか」を \(O(n^3)\) で求める。DPの遷移は、最後に塗るマス \(k\) を決めて分割する。
P5662 [CSP-J2019] 記念品
完全ナップサックDP。\(i\) 日目から \(i+1\) 日目への資金の増加を最大化する問題とみなす。毎日、全アイテムに対して完全ナップサックを実行し、資金を更新する。
P11232 [CSP-S 2024] 超速検測 T2
加速度が正の場合と負の場合で分けて考える。第1問は各車両について監視可能か判定すればよい。第2問はカバーすべき区間を求め、最小の点（監視カメラ）で全ての区間をカバーする問題（区間スケジューリングの問題）に帰着される。
P11233 [CSP-S 2024] 染色 T3
\(dp[i]\) を「最後に \(i\) 番目の要素を \(i+1\) 番目の要素と異なる色で塗った場合の最大値」と定義する。遷移には、同じ色が連続する場合のスコア（\(a_k = a_{k+1}\) なら \(a_k\) を加算）が含まれる。このスコア部分をデータ構造（Segment Treeなど）で管理することで \(O(n \log n)\) に高速化できる。
MZOJ #1021 簡単問題
費用流問題。各点を左ノードと右ノードに分割し、始点から左ノードへ、右ノードから終点へ、そして左ノードから支配可能な右ノードへ辺を張る。最小費用流を求める。
P3410 撮影
最大重み閉部分グラフ問題。各ノードの重みが正の場合は始点から、負の場合は終点へ、絶対値の重みの辺を張る。元のグラフの辺は無限大の容量で張る。全ての正の重みの和から最小カットを引いた値が答えとなる。
[AGC061C] First Come First Serve
包除原理を用いる。区間が入れ子になっている場合、順序を入れ替えられるため、答えが増加する。DPを用いて、入れ子関係にある区間の影響を除外しながら数え上げる。
MZOJ #1053. 画家
ビットセットを用いて、各色の出現回数の偶奇を管理する。平方分割（Mo's algorithmなど）を用いて、各区間のビットセットを管理する。木上のパスについては、オイラーツアー（Euler Tour Technique）を用いて列に変換する。
以下、いくつかのスライド最小値（Monotone Queue）最適化DP。
P3572 [POI2014] PTA-Little Bird
スライド最小値の典型問題。DPの遷移式は、直近 \(k\) 個の状態から遷移する。スライド最小値を用いることで、状態遷移を \(O(qn)\) から \(O(n)\) に改善できる。
P2569 [SCOI2010] 株式取引
DPの状態は \(dp[i][j]\)（\(i\) 日目に \(j\) 株持っている場合の最大利益）と定義する。購入・売却の遷移は、直近の \(w\) 日前からの状態を参照する。この遷移をスライド最小値で高速化する。
P2034 数字選択
DPの遷移は、直近 \(k\) 個の状態から遷移する。優先度付きキューまたはスライド最小値で最適化する。
P2254 [NOI2005] 瑰麗なるワルツ
DPの状態を \(dp[k][x][y]\)（\(k\) 番目の時間帯に \((x,y)\) にいる場合の最大移動距離）と定義する。各時間帯の移動方向が固定されているため、遷移は直近の \(len\) 個の状態から遷移する。この遷移をスライド最小値で高速化する。
P3800 Power収集
スライド最小値の典型的な問題。各セルへの移動は直近 \(T\) 個のセルから可能であり、スライド最小値で処理できる。
以下、いくつかの木DP（ナップサックDPを含む）。
P1272 再建道路
\(dp[u][i]\) を「頂点 \(u\) の部分木からサイズ \(i\) の部分木を切り出すための最小切断辺数」と定義する。子の部分木からサイズを配分するナップサックDPを行う。
P2015 二叉林檎樹
辺の重みを子ノードの重みに変換し、ナップサックDPを行う。
P4516 [JSOI2018] 潜入行動
状態 \(dp[u][i][a][b]\) を定義する。\(a\) は \(u\) に機器を設置したか、\(b\) は \(u\) が監視下にあるかを示す。遷移は複雑で、4つの状態の組み合わせを考慮する。複雑度は \(O(nk)\)。
P1273 有線電視網
\(dp[u][j]\) を「頂点 \(u\) の部分木から \(j\) 個の葉ノードを選択した場合の最大収益」と定義する。ナップサックDPの典型的な問題。
P3874 [TJOI2010] 伐採
01分数計画法を用いる。価値と重みの比を最大化するために、二分探索とナップサックDPを組み合わせる。
P4322 [JSOI2016] 最佳団体
上記の問題と類似しており、01分数計画法とナップサックDPを用いる。
P3177 [HAOI2015] 樹上染色
各辺の寄与を考慮したナップサックDP。辺の両側の黒頂点の数と白頂点の数の積が、辺が答えに与える影響となる。
P4037 [JSOI2008] 魔獣地図
合成操作があるため、状態に「いくつ自分を残すか」という情報を追加する。\(f[u][j][k]\) を「頂点 \(u\) の部分木から \(j\) 個の \(u\) を残し、合計 \(k\) 円使った場合の最大値」と定義する。
MZOJ #1047. 分割
最小値の最大化問題は、二分探索で判定問題に変換する。判定問題は、各要素を順に処理しながら、条件を満たす分割が可能かをチェックする。
MZOJ #1070. 縱使日薄西山（xor）
4つの数のXORを直接扱う代わりに、2組のペア \((a_1, b_1)\), \((a_2, b_2)\) のXORが等しくなる場合を数える。XORの値をキーとして連想配列で管理する。数え上げの際には重複を排除するために、3で割る必要がある。
MZOJ #1076. room
障害物の削除に関する場合分けを行う。2つの障害物を削除する場合、それらが連結成分を形成するかどうかをUnion-Findで判定する。
MZOJ #1074. swap
\(k\) が非常に大きい場合、桁数の大きい数（大きな値）を後ろの方に移動させるのは非効率である。したがって、大きな値を先頭に移動させる。残りの少ない桁数については、\(O(n^2)\) の操作で最適化する。
P2470 [SCOI2007] 圧縮
区間DP。状態 \(dp[l][r][0/1]\) を「区間 \([l, r]\) を \(M\) を内部に含めない/含める場合の最短長さ」と定義する。\(M\) の位置、および区間が繰り返しパターンを持つ場合の圧縮を考慮する。
P2679 [NOIP2015 提高组] 部分文字列
DPの状態 \(dp[i][j][k]\) を「\(A\) の \(i\) 文字目まで、\(B\) の \(j\) 文字目までを \(k\) 個の部分文字列でカバーする場合の数」と定義する。遷移を累積和で高速化し、さらに空間を節約するために転置（rolling array）を用いる。
P10194 [USACO24FEB] Milk Exchange G
（問題文が不完全のため、解答不能）
P2986 [USACO10MAR] Great Cow Gathering G
リルートDP（全方位木DP）の典型問題。根を頂点1として一旦計算し、その後、各隣接ノードへの移動に伴う値の変化を計算する。
P1850 [NOIP2016 提高组] 教室を変える
状態 \(dp[i][j][0/1]\) を「\(i\) 番目の授業までに \(j\) 回教室変更を申請し、\(i\) 番目の授業の教室を変更したかどうか」と定義する。遷移には、変更申請が成功する確率と失敗する確率を考慮する。事前にワーシャル–フロイド法で全点対間最短距離を求めておく。
P1156 ゴミ罠
状態 \(dp[j]\) を「高さ \(j\) に達したときの最大生命力」と定義する。各ゴミについて、食べるか積むかの2択のナップサックDP。生命力が0以下にならないように注意する。
P2607 [ZJOI2008] 騎士
キレイな木の森（Functional Graph）上の最大重み独立集合問題。各連結成分にはちょうど1つの辺が多く存在する（サボテン）。その辺の両端点を根としてDPを行い、その2つの結果のうち、両方の根を同時に選択しない場合の最大値を取る。
MZOJ #1083. 物流（logistics）
エッジ数が多いため、まずは最小全域木（MST）を求め、その辺のみを保持する。各クエリで追加される辺と、MSTの辺を合わせて再度クラスカル法を実行する。
P4158 [SCOI2009] 粉刷職人
1行分のDP（\(dp[i][j]\)：先頭 \(i\) マスを \(j\) 回塗った場合の正しく塗れたマス数）をまず求め、その後、行間のDP（\(g[i][j]\)：最初の \(i\) 行を \(j\) 回塗った場合の最大値）をナップサックDPで求める。
P1772 [ZJOI2006] 物流運輸
\(val[i][j]\) を「\(i\) 日目から \(j\) 日目まで同じ経路を使い続ける場合の1日あたりの最小コスト」と定義する。\(dp[i]\) を「最初の \(i\) 日間の最小コスト」と定義し、\(val\) を用いて遷移する。
P3554 [POI2013] LUK-Triumphal arch
二分探索を用いる。判定問題は、各頂点において、子の部分木を制圧するために必要な追加のマーク数を計算する木DPを行う。
P10653 「ROI 2017 Day 2」記憶装置
極大な連続部分列を縮約し、スタックを用いて処理する。各操作（符号の反転、合体）は全体で \(O(n)\) となる。
P8865 [NOIP2022] 植花
平面走査の要領で、各マスを左上とするC型・F型の花の個数を、前処理（各マスから右方向・下方向に連続する0の個数）を用いて \(O(n^2)\) で計算する。
P1073 [NOIP2009 提高组] 最適貿易
強連結成分分解（SCC）を行い、DAG上でDPを行う。各成分の最小価格と最大価格を保持し、トポロジカル順に更新する。
P1841 [JSOI2007] 重要な都市
ワーシャル–フロイド法で、各点対間の最短経路の本数も同時に数える。ある点 \(k\) が \(i\) から \(j\) へのすべての最短経路に含まれるならば、\(k\) は重要である。