Educational DP Contest / DP まとめコンテスト

更新日時:

Educational DP Contest / DP まとめコンテスト

ぼちぼち解いていきます。

ソースコード

解法のメモ

基本は $0$-indexed とする。

A - Frog 1

$DP[i] = i$ 番目に至るコストの総和の最小値

とする。初期状態: $DP[0] = 0$, $DP[i] = \infty$ ( $i \geq 1$ ) 、答え $DP[N - 1]$ である。

遷移は以下の通り。 $i = 0, \dots, N - 2$ に対し、 $j = i + 1, i + 2$ に対し、 $j \leq N - 1$ ならば $DP[j] \gets \min(DP[j], DP[i] + \lvert h _i - h _j \rvert )$ とする。

ポイント

この問題は人をバカにするほどには易しすぎず、しかし難しすぎない、いい問題だと思う。

B - Frog 2

上の解法を $j = i + 1, \dots, \min(N - 1, i + K)$ に変更するだけである。

ポイント

これもいい問題ですね。 A が B の発展形であることが自然にわかる。

C - Vacation

ポイント

D - Knapsack 1

ポイント

E - Knapsack 2

ポイント

F - LCS

ポイント

G - Longest Path

ポイント

H - Grid 1

ポイント

I - Coins

ポイント

J - Sushi

ポイント

K - Stones

ポイント

L - Deque

ポイント

M - Candies

ポイント

N - Slimes

ポイント

O - Matching

ポイント

P - Independent Set

ポイント

Q - Flowers

ポイント

R - Walk

ポイント

S - Digit Sum

ポイント

T - Permutation

ポイント

U - Grouping

ポイント

V - Subtree

ポイント

W - Intervals

ポイント

X - Tower

ポイント

Y - Grid 2

ポイント

Z - Frog 3

ポイント

その他