DP力が貧弱なので、EDPCの解き直しをしつつ、記録を残します。
結構自力で解けてないやつもあるので、解けてない問題は解け次第随時更新となります。
めっちゃネタバレ記事になる予定なので、これから自力で解こうという方はぜひブラウザバックを…

A - Frog 1

$DP _ {i} := i$ 番目の足場に辿り着くのに必要な最小スコア

とすればよい。ジャンプ先はたかだか2つしかないので、配るDPで $i+1, i+2$ に向かってスコアを更新していけば、 $DP_ {N}$ が解となる。

Submission #38476589 - Educational DP Contest

B - Frog 2

DP配列の定義、更新の仕方ともにA問題と同様でよい。A問題はジャンプ先がたかだか2つだったが、今回は最大100個くらいジャンプ先がある(さらに個数は可変)ので、二重ループで実装する必要がある。
時間計算量は $O(NK)$ となるが、 $NK \le 10 ^ {7}$ 程度なので、(よほど低速な言語でない限りは)余裕で間に合う。

Submission #38476657 - Educational DP Contest

C - Vacation

単純に考えると、

$DP _ {i} := i$ 日目までに得た幸福度の最大値

とすれば良さそうだが、二日連続で同じ活動はできないので、日付だけでなく、その日の活動の種類もパラメータとして持っておかないといけない。
なので、

$DP _ {i, kind} := i$ 日目の活動が $kind$ であったときの $i$ 日目までに得た幸福度の最大値

とすればよい。日付を昇順に見つつ、前日の活動と当日の活動を二重ループで回し、前日と活動がかぶらないときだけ更新していく。

Submission #38476742 - Educational DP Contest

D - Knapsack 1

$W$ がそんなに大きくないので、

$DP _ {i} :=$ 容量 $i$ まで品物を詰めたときに実現できる価値の総和の最大値

とすればよい。DP配列を適切に更新すれば、何番目の品物まで詰めたかをパラメータとして持つ必要はない。(具体的には、品物ごとにDP配列を後ろから更新すれば、重複更新しないで済むようになる)
時間計算量は $O(NW)$ 程度になる。

Submission #38476804 - Educational DP Contest

E - Knapsack 2

D問題と違って $W$ はとても大きいので、同じように解くことはできない。
しかし、代わりに各 $v _ {i}$ はとても小さく、 $N$ の制約と合わせても価値の総和はたかだか $10 ^ {5}$ 程度になるので、

$DP _ {i} :=$ 選んだ品物の価値の総和が $i$ であるときの重さの総和の最小値

とすればよい。最終的に、値が $W$ 以下であるようなDP配列のインデックスが解となる。
時間計算量は $O(N \sum v)$ (どうでもいいが、この表記が正しいのかはよくわからない…)

Submission #38476933 - Educational DP Contest

F - LCS

問題名の通り、文字列 $s, t$ のLCS(Longest Common Subsequence)を求める。
超ド典型なので、私が頑張って説明するより既存の記事を見たほうが正確でわかりやすいため、細かい説明はカット。

$DP _ {i, j} :=$ 文字列 $s$ の $i$ 文字目、文字列 $t$ の $j$ 文字目まで見たときのLCSの長さ

としてDP配列を埋めていく。今回は復元が必要なので、 $DP _ {len(s), len(t)}$ からDP配列を埋めるのと逆回しに見ながら、LCSの長さが増えるタイミングで文字を拾っていくと、答えが求まる。

Submission #38477139 - Educational DP Contest

G - Longest Path

グラフの各連結成分はDAGなので、トポロジカル順序が定義できる。
なので、

$DP _ {i} :=$ 頂点 $i$ を終点とする有向パスの最大の長さ

として、トポロジカル順序が早いものから順にDP配列を埋めることで答えが求まる。実装としては、入次数0の頂点から枝を刈りつつ、到達可能頂点のDP配列の値を更新するような感じ。
時間計算量は $O(N + M)$ 。

Submission #38477359 - Educational DP Contest

H - Grid 1

どうみてもやるだけだが…本当にやるだけ。

$DP _ {i,j} :=$ 問題文中の条件を満たしつつ座標 $(i, j)$ に到達する経路数

行方向、列方向どちらを優先して更新しても正しい答えは出ると思うが、上→下、左→右の方向は守らないと正しい答えは出ない。(まさかあえて下→上とか右→左に更新する人なんていないと思うが…)
時間計算量は $O(HW)$ 。

Submission #38479171 - Educational DP Contest

I - Coins

コインはすべて区別されるので、独立した事象としてよい。また、どのコインが裏であるとか表であるとかには関心はなく、単に表の枚数がわかっていれば十分である。
なので、コインは順番に投げられたとして、

$DP _ {i} :=$ 表のコインが $i$ 枚出る確率

とすればよい。ナップザックDPと同じで、DP配列を使いまわせば、何枚目のコインまで投げたかのパラメータは必要ない。
新しいDP配列を $New$ とすると、 $New _ {i}$ += $DP _ {i} * (1 - p), New _ {i+1}$ += $DP _ {i} * p$ と更新することで、最終的なDP配列の $N / 2 + 1$ 番目以降の値の和が答えとなる。
時間計算量は $O(N ^ {2})$ 。

Submission #38479356 - Educational DP Contest

J - Sushi

個人的難関ポイント。期待値DPは本当に苦手…
なんとなく、

$DP _ {i, j, k} :=$ 寿司1個、2個、3個の皿の残り枚数が $i$ 枚、 $j$ 枚、 $k$ 枚であるときの初期状態からの操作回数の期待値

としたくなるが、期待値DPは後ろから考えたほうが見通しが良くなることが多い。具体的には、

$DP _ {i, j, k} :=$ 寿司1個、2個、3個の皿の残り枚数が $i$ 枚、 $j$ 枚、 $k$ 枚であるときの残り操作回数の期待値

とする。このとき、 $DP _ {0, 0, 0} = 0$ が初期状態となり、漸化式は、

$DP _ {i, j, k} = DP _ {i-1, j, k} * i / N \\ + DP _ {i+1, j-1, k} * j / N \\ + DP _ {i, j+1, k-1} * k / N \\ + DP _ {i, j, k} * (N - i - j - k) / N \\ + 1$

となる。だいぶ見にくくなっているが、右辺の1項目は寿司1個の皿、2項目は寿司2個の皿、3項目は寿司3個の皿を選ぶことに対応している。4項目は寿司0個の皿を選んでしまった場合で、このときはどこにも遷移できない。
右辺にも左辺と同じ式が現れて循環してしまっているが、これは移項して整理することができる。
最終的な遷移式は以下のようになる。

$DP _ {i, j, k} = (DP _ {i-1, j, k} * i + DP _ {i+1, j-1, k} * j + DP _ {i, j+1, k-1} * k + N) / (i + j + k)$

注意として、添え字の形がだいぶ歪なので、何も考えずに外側から $i, j, k$ とループすると正しい答えが出ない。
また、これも何も考えずにDP配列のサイズを初期の寿司1個、2個、3個の皿の枚数で決めると正しい答えが出ない。実際には寿司2個の皿は最大で (寿司2個の皿の枚数 + 寿司3個の皿の枚数)となるので、これを考慮してDP配列のサイズを決める必要がある。(寿司1枚の皿についても同様。)
時間計算量は $O(N ^ {3})$ 。低速な言語だとちゃんと枝刈りをしないとTLEすると思われる。(Rustでもテキトーな実装だとキツかった)

Submission #38481791 - Educational DP Contest

K - Stones

いわゆる後退解析と言われるやつ。こういうのは遷移の順番がめちゃくちゃなので、以下のようにメモ配列を定義してメモ化再帰する。

$Memo _ {i} :=$ 石の個数が $i$ であるときに先攻でゲームを始めた場合の勝敗

列挙体でも数値でもなんでもいいと思うが、列挙体を定義するのが面倒だったので $0 =$ 未決定、 $1 =$ 勝ち、 $2 =$ 負けで定義した。
若干頭が混乱するので、列挙体で名前を付けたほうが良かったかも。
時間計算量は $O(NK)$ 程度。(実際はもっと軽い気はする)

Submission #38482920 - Educational DP Contest

L - Deque

これもメモ化再帰で実装するのが楽そう。以下のようにメモ配列を定義する。

$Memo _ {i, j} :=$ 残った要素が配列 $A$ のうち半開区間 $[i..j)$ の要素であるときに先攻としてゲームを始めた場合のスコアの最大値

再帰関数は相手の実現できる最大のスコアを返してくるため、pop_front, pop_backそれぞれの場合について、取り出した要素から相手のスコアを引くことで、自分の実現できるスコアを計算できる。
この2通りのうちの最大値が自分のスコアになるので、これをメモしたうえで返せばよい。
時間計算量は $O(N ^ 2)$ 。

最初、メモ配列を雑にHashMapで持っていたら危うくTLEしかけたが、配列に変えただけで10倍以上高速になった。HashMapどんだけ遅いねん…

Submission #38483378 - Educational DP Contest

M - Candies

遷移先が範囲なので、なんとなくimos法を使いたくなる。実際、これで解ける。

$DP _ {i} :=$ 合計 $i$ 個の飴を配る方法の数

誰まで見たかをパラメータとして持つ必要はなく、配列の使いまわしで対応する。新しい配列 $New$ を0初期化しておいて、

$New _ {i..i+a} += DP _ {i}$

みたいなことができると嬉しいので、ここでimos法を適用してやることで計算量を抑える。
計算量は $O(NK)$ 。

Submission #38487063 - Educational DP Contest

N - Slimes

スライムの合体を区間のマージとして見ることで、区間DPをすることを考える。

$DP _ {i, j} :=$ 区間 $[i..j)$ に含まれるスライムを1つのスライムとして合体させるためのコストの総和の最小値

コストとスライムの大きさは一致しないので、DP配列をタプルで持ったり、区間内のスライムのサイズの総和を持った配列を別で持つ必要がある。
スライムのサイズの総和は $O(N ^ {2})$ で求まるが、制約が緩いので雑に $O(N ^ {3})$ で求めても良い。
どちらにしても区間DPを行うパートが計算量を支配するので、全体としての時間計算量は $O(N ^ {3})$ 。

Submission #38487447 - Educational DP Contest

O - Matching

制約はbitDPしろと言っているようにも感じるが、考えてみるとちょっと悩ましい。
結論、男性は前から順番に決めて、ペアの決まった男性に対してどの女性をマッチさせるかをbit集合で持つこととし、以下のようにDP配列を定義する。

$DP _ {i, S} :=$ 男性 $i$ までマッチを確定させたとき、マッチ済の男性のいずれかにマッチしている女性の集合が $S$ であるような場合の数

雑にやると、外側で男性を順に確定させるループを回し、男性にマッチ可能な女性を決め打ってbit集合の遷移を作ることで $O(N ^ {2} 2 ^ {N})$ が実現できる。

結果としてはこれでACできるが、Rustで1700msecもかかっているので、明らかに想定の解法とは思えない。
その後、一度もマッチしていない女性を含んだ集合からの遷移を刈ったり、これから集合に加えようとする女性を含んだ集合からの遷移を刈ったりすることで700msecくらいまでは縮んだが、計算量自体は落ちていない気がする…要再考。

Submission #38488127 - Educational DP Contest

P - Independent Set

以下のような木DPを考え、葉から再帰的に答えを導く。

$DP _ {i, color} :=$ 頂点 $i$ の色が $color$ のとき、頂点 $i$ を根とする部分木の色の塗り方の場合の数

頂点を白に塗った場合、子は白でも黒でも良いので、両方の場合の数の和の総積が答えとなる。頂点を黒に塗った場合、子は白でなければならないので、子が白の場合の数の総積が答えとなる。
最終的に、木の根について白であった場合の数と黒であった場合の数の和が全体としての答えとなる。
時間計算量は $O(N)$ 。

Submission #38488740 - Educational DP Contest

Q - Flowers

以下のようにDP配列を定義し、前から答えを確定させることを考える。

$DP _ {i} := i$ 本目以前の花の抜き去り方を確定し、 $i$ 本目の花を残す場合の花の美しさの総和

単純に考えると、 $i$ 本目の花を見るとき、1本目から $i-1$ 本目の花をすべて見て、高さが $i$ 本目の花より低ければ遷移して最大値をとる、とすれば答えは求まるが、それでは時間計算量が $O(N ^ {2})$ となりTLEする。
さらに考えると、 $i$ 本目以前の $i$ 本目の花より高さの低い花すべてについてDP配列の値の最大値が求まればよいので、花の高さをインデックスとした、範囲maxをさばくセグメント木を用いて高速化できる。
時間計算量は $O(N \log N)$ となる。

Submission #38489293 - Educational DP Contest

R - Walk

制約メタ読みと当てずっぽうでACしてしまったが、原理は理解できていない…要再考。

結論だけ言えば、配列 $A$ をそのまま行列とみて、行列累乗 $A ^ {K}$ を計算し、要素の総和を取ることで答えが出る。
時間計算量は $O(N ^ {3} \log K)$ 。

Submission #38489671 - Educational DP Contest

S - Digit Sum

いわゆる桁DPというやつ。個人的には若干苦手意識がある。

$DP _ {i, j, k} := K$ の $i$ 桁目までみたとき、総和を $D$ で割った余りが $j$ であり、現時点で $K$ と等しいか否かのフラグが $k$ である場合の数

としてDP配列を前から埋める。
現時点で $K$ と等しい場合、 $i+1$ 桁目は $K$ の $i+1$ 桁目以下でなくてはならないところだけ注意し、各桁で $j, k$ を全探索すれば、最終的に $DP _ {N, 0, 0} + DP _ {N, 0, 1} - 1$ が答えとなる。
全桁0は数に含んではいけないが、 $D$ で割った余りは $0$ なので、答えに誤って含まれないように $1$ を引くことを忘れてはいけない。

時間計算量は各桁の種類数を $digits$ として、 $O(ND * digits)$ 。

ついすべての桁のDP配列を用意してしまっているが、これも配列を使いまわせばもっと省メモリで実装できる。

Submission #38512194 - Educational DP Contest

T - Permutation

無理だった…完敗。解説ACした。
DP配列の定義としては、

$DP _ {i, j} := i$ 番目まで並べ方を確定させて、 $i$ 番目に選んだ数字未満の数字が $j$ 個残っているような並べ方の数

とする。
すると、'>'のとき、残っている数字のうち、1番目から $j-1$ 番目までの数字を選べるので、

$DP _ {i+1, [1..j)} += DP _ {i, j}$

となる。
同様に、'<'のとき、残っている数字のうち、 $j+1$ 番目から $N-i$ 番目までを選べるので、

$DP _ {i+1, [j..N-i)} += DP _ {i, j}$

となる。
ここまでの段階で時間計算量は $O(N ^ 3)$ を実現できる。(状態数が $O(N ^ 2)$ 、遷移に $O(N)$ 時間かかるため)
ここで、1回のDPの遷移は区間への加算となるので、M問題と同様にimos法を使って計算量を抑えられるため、最終的には時間計算量 $O(N ^ 2)$ を実現できる。