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

AtCoder

https://atcoder.jp/contests/dp

 

A Frog 1

dp[i] = 足場iに着くまでの最小コスト　とすると

足場i-1か足場i-2から飛んでくる場合の2通りなので

dp[0] = 0

dp[i] = min(dp[i-1] + |h_i - h_i-1|, dp[i-2] + |h_i-h_i-2|)

となり。iの昇順にdp[i]を計算する。

B Frog 2

同上

C Vacation

 その日に取れる選択は前日の活動にのみ依存するので

dp[i][j] = i-1日までに直前の活動がjの時の最大幸福度

D Knapsack 1

dp[i][w] = 品物iまでの中から選び合計重さがwになるときのの最大価値

E Knapsack 2

dp[i][v] = 品物iまでの中から選びに合計価値がvになるときのの最小重さ

F LCS

dp[i][j] = s[1..i]とt[1..j]の最長共通部分列長

G Longest Path

トポロジカルソートしてDPでも解ける

メモ化再帰のほうが楽

H Grid 1

GridDP dp[x][y] = (x,y)に到達する経路の数

I Coins

確率DP dp[i][j] = i枚投げてj枚表が出る確率

J Sushi

期待値DP

寿司が同じ個数の皿を区別する必要がないのでdp[１個の皿の枚数][2個の皿の枚数][3個の皿の枚数] = 期待値とする

 

 K Stones

２人ゲームは相手に必敗の状態を押し付ければ勝ちなので

dp[k] = 必勝か必敗

として各dp[k]は dp[k - x] が必敗となるx<aが存在するかで更新していく

L Deque

 dp[残ってる先頭][残ってる最後尾] = X - Y

残ってる区間の長さからどちらのターンかわかるので最小化あるいは最大化する手を選ぶ

M Candies

dp[i][j]=i-1人目まで配って計j個配った時の場合の数　区間和差分　O(NK)

飴を0~a[i]個までの範囲で配れるため区間に足しこむ処理が必要。

長さa[i]の区間和を更新していくか、いもす法を使う。

N Slime

区間DP O(N^3)　蟻本P121

O Matching

O(N^2 * 2^N )だとTLEする。

dp[マッチンング済み女性のビット集合] = 場合の数

として昇順にループを回し

「popcount(女性のビット集合) 番目の男性」と「各相性の良い女性」で遷移するとO(N * 2^N )になる

P Independent Set

木DP

葉から塗っていくときある頂点を塗れるかは子が白か黒かにのみ依存する。

dp[頂点][白か黒か] = 場合の数

Q Flowers 2

データ構造

dp[H] = 末尾の花の高さがHのときの美しさの総和の最大値

とすると花を左から見ていくことで dp[h[i]] = max(dp[h[i]], dp[0 ~ h[i]-1] + 1)

となる。区間のmaxをの取得と更新は binary indexed tree や segment treeといったデータ構造を使うことでO(log N)になる。

R Walk

行列累乗　蟻本P183

S Digit Sum

digit DP

上の桁から数字を決めていくときの状態遷移には2通りあり、具体的には

K=12345 で123...まで決まっているとき4桁目は4以下しか選べないのに対して

122..だとすべての数字をとりうる。

dp[i][一度でも各桁を下回ったかのフラグ][数字の総和 mod D] = 場合の数として

T Permutation

先頭から順に決めていくとき状態遷移は最後に使った値の残ってる値の中での順位によってまとめることができる。

dp[i][j] = i個まで使って最後に使った値より大きい値がj個あるときの場合の数

O(N^2)で解ける

U Grouping

ビット演算で部分集合列挙するテク　O(3^N)　蟻本P144

V Subtree

全方位木DP

逆元はないので左右からの累積和を使う

全方位木DPについてはググって

W Intervals

dp[i] = i番目を最後に1にしてからj 番目を1にしたときのスコアの最大値

としてdpテーブルをsegtreeで更新していき、各jについてのdpテーブルを計算する。

X Tower

s_i+w_i で非自明ソートしてDPするやつ

Y Grid 2

太郎君の経路数 = 壁を無視した全経路数 - 壁を１か所でも通る経路の数

なので壁を１か所でも通る経路をDPで求める。

壁iに来る経路の数は  \binom{X_i+Y_i}{X_i}となるが左上にも壁がある場合そこから来る経路もあるため重複して数えることになる。

そのためまず壁を (X_i, Y_i)で辞書順ソートすることで左上の壁が小さいインデックスに来るように移動させる。

dp[i] = 初めて到達する壁が壁iであるような経路の数

としてdp[i]は  \binom{X_i+Y_i}{X_i}から左上にある壁j(j < i) を見ていき dp[j] *  \binom{X_i-X_j+Y_i-Y_j}{X_i-X_j}

を引いていくことで重複なく計算できる。

最後に各dp[i]から(H,W)までの経路の総和が壁を１か所でも通る経路の数になる。

 

Z Frog 3

Convex Hull Trick

蟻本読んで