DP まとめコンテスト

※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※
自分の「解法」は肝の部分しか書いてないので、
細かい部分はご自身で補間する必要があると思います。
（ソースコードを覗いてみるというのもアリ）
解説というよりはヒントだと思って読むくらいがちょうど良いでしょう。
※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※

A: dp[i] = 場所 i に行くminコスト

B: 〃

C: dp[i][j (0~2)] = i 日目に j (=A~C) をするときのmax

D: dp[i][j] = i 個目までで重さ j にするときのmax価値

E: dp[i][j] = i 個目までで価値 j にするときのmin重み

F:
dp[i][j] = s[0~i], t[0~j] までのLCS、復元は i=|s|, j=|t| からスタートして答えの辻褄が合う遷移を逆に辿っていく

G:
トポロジカルソート（dfsで帰りがけ順をつけていく等）してから、dp[v] = v で終わるパスの最大長
追記>メモ化再帰でやればトポロジカルソート要らないんですね。すごい。

H: dp[i][j] = (i,j) まで行く場合の数

I:
dp[i][j] = i 回投げて 表-裏 が j の確率。添字は負になりうるので下駄を履かせる。（あるいは配列がポインタであることを利用して負の添字で正しく動くようにするテクもあるけどかえって混乱しそう）
追記＞別に j を表の回数とかにしても良いのでその方が楽そうですね。

J:
dp[i][j][k] = 残ってるのが 1,2,3 個の皿が i,j,k 個ある状態からの期待値。自分自身への遷移は困るので、x=a*p+x*q → x(1-q) = a*p → x = a*p/(1-q) のように右辺から自分自身を消すこと。

K:
dp[i] = i 個残った状態からどっちが勝つか。負け＝相手が負ける状態に行けない

L: dp[l][r] = l~r が残った状態からの 先手-後手 のmax。

M:
dp[i][j] = i 人目までに j 個配る場合の数。累積和を使って遷移を高速化する。

N:
区間DP。dp[l][r] = l~r を１つのスライムにする最小値。遷移は分割位置 k をl~r-1で試してchmin(dp[l][r], dp[l][k]+dp[k+1][r]+マージコスト)。

O:
dp[i][S] = i 人目の男性までマッチングしてに既に決まった女性の集合がSの場合の数。S は二進数で持つと良い。よく考えると i = pop_count(S) なので i は要らない。O(2^n * n)

P:
木DP。dp[v][i (0,1)] = 頂点 v 以下の部分木を塗り分けて、v の色が i である場合の数。

Q:
重み付きLIS（っていうのかな）dp[i] = 最後に選んだ花の高さが i であるときのmax。遷移は dp[h[i]] = max(dp[j] | j = 0~h[i]-1)。segtreeなどで高速化する。O(N log N)

R:
行列累乗。dp[i][v] = 長さ i で頂点 v で終わるパスの個数。行列累乗で高速化する。T を隣接行列として、dp[i] = dp[0]*(T^K)。O(N^3 log K)

S:
桁DP。dp[i][j][k (0,1)] = 上から i 桁目まで決めて桁和 mod D が j で、K と一致している(k=0) or K 未満になることが確定した(k=1)、である場合の数。もう少し複雑になったらメモ化再帰で書いた方が綺麗に書けたりする。

T:
dp[i][j] = i 個目までを 0~i-1 の順列で作って末尾が j である場合の数。挿入DPっぽい感じ。

U:
dp[S] = 残りの集合が S であるときの max。遷移は S の部分集合 T を全部試せばいい。計算量は、内側のループを通ったとき各bitについての(Sに含まれない, Sだけに含まれる, Tに含まれる)の 3 通りの組み合わせが 1 回ずつ現れるのでO(3^N)。dp2[S] = 集合 S を１グループにした時の点数、も前計算しておくと良い。こちらはdp[Sの最下位bitを取り除いたもの]から遷移すると良い。
追記＞部分集合の列挙は for (int t = s; t != 0; t = (t-1)&s) というようにビット演算を駆使すると綺麗に書けます。(空集合も必要な場合はfor文内の最後にif (!t) break とかする)

V:
全方位木DP。dp[有向辺] = 辺(u→v)について、v 以下の部分木を根が黒になるように塗る場合の数、を全部求めればできる。根付き木にしてDFSすると、親→子方向の辺については全部求められる。ここで、根から出る辺については全部求まっているので、そこから根→子の辺について求められる。するとその子についても全部求められていて...という風にBFSっぽくやると子→親方向の辺についても全部求められる。「〜全部求まっているので、そこから〜」の部分は、DPが和とかなら「総和を求めて、親→子方向の辺についての値を引く」とすればいいのだが、積なので割り算ができない。子を一列に並べて、0~iの積とi~|子|の積みたいなのを前計算しておくと、１個だけを除いた値が計算できるようになる。（１行で説明するには厳しすぎる）O(N)

追記>注意点として、仮にmodが素数でも割り算は出来ません。(部分木の答えは0(modで)に出来うるため)

W:
dp[i] = （i まで決めたときに）最後に1にしたのが i であるときのmax。遷移は dp[i] = min(dp[j] | j=0~i-1) 。その後、区間 [l,i] について dp[l~i] に a を足しこむということをやる。segtreeで高速化する（区間addと区間minができれば良い）O((N+M) log N)
なんかこれは自分は典型化できてなかった（ので説明がふわっとしてしまっている）

X:
DPはおまけ。使う集合を決めたとき、どういう順で積むべきか考える。隣接した２つのブロック (w_i,s_i) と (w_j,s_j) があって i を上に置ける条件は C+w_i<s_j で、j を上は C+w_j<s_i (C=上に積んであるものの重さの和)。i を上に置いた方が C をより重くできる条件は s_j-w_i > s_i-w_j で、移項すると s_j+w_j > s_i+w_i つまり、s_i+w_i の昇順に上から並べていけばいい、となる。（この条件を満たしてない並べ方は、満たしていない箇所をswapすることによってより"良い"並べ方にできるため最善でないといえる）あとは自明DP。

Y:
除DP（包除の包はなく除しかしない）。点を(r,c)の昇順に並べておく。dp[i] = i-1 個目までの点を通らず、i 個目の点を通る場合の数。O(N^2)
追記＞遷移は f(r,c) を(0,0)から(r,c)までの経路数として、 dp[i] = f(Ri-1,Ci-1) - Σ(dp[j] * f(Ri-Rj, Ci-Cj) | 点 j が点 i の左上にある)

Z:
Convex Hull Trick。dp[i] = min(dp[j]+(h[i]-h[j])^2+C | j = 0~i-1) を高速化する。式を展開すると、dp[j]+(h[i]-h[j])^2+C = (dp[j]+h[j]^2) + (h[i]^2+C) - (2*h[i]*h[j]) となり、結局 min(A_j*x + B_j) みたいな一次関数の最小化みたいな形なのでCHT。あとは蟻本読んで。O(N)


おまけ： https://docs.google.com/spreadsheets/d/10d8I-x5EzXxWGgviOueCnWYPyJ_QrJlZELeZTP6g3L0/edit?usp=sharing