kurarrr's memooo

主に競プロ備忘録

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

AtCoder DP DPのkeyの変換

メモ

17完. 解けない問題いっぱいあるなあ
集めるDPの方がバグらせにくくて(当社比),メモ化にもしやすいのでほぼそっちで書いた.
簡潔なまとめはプロのツイッターを見るのが良い.

A

dp[ i ] := min( dp[i-1] + cost(i-1,i), dp[i-2] + cost(i-2,i) )
cost(i,j) = abs( h_i - h_j )
O(N).

Submission #3936500 - Educational DP Contest

B

dp[ i ] := min_{ i-K <= j < i } ( dp[ j ] + cost(j,i) )
cost(i,j) = abs( h_i - h_j )
O(NK).

Submission #3937040 - Educational DP Contest

C

dp[ i ][ j ] := max( 現在 i-1 日目 で 前日に j 番目の活動をした時の幸福度 )
dp[ i ][ j ] = max_{ k != j }( dp[ i-1 ][ k ] + h[ i ][ k ] )
h[ i ] = { a_i, b_i, c_i }
O(N).

Submission #3937463 - Educational DP Contest

D

dp[ i ][ j ] := max( i-1 番目まで入れるか決めて重さ j の時の価値の総和) dp[ i ][ j ] = max( dp[ i-1 ][ j ], ( j - w_i >= 0 ? dp[ i-1 ][ j - w_i ] : -INF) )
O(NW).

Submission #3937463 - Educational DP Contest

E

dp[ i ][ j ] := min( i-1 番目まで入れるか決めて価値 j の時の重さ)
dp[ i ][ j ] = min( dp[ i-1 ][ j ], ( j -v_i >= 0 ? dp[ i-1 ][ j -v_i ]: INF ) )
O(N sum(v_i )).

Submission #3938707 - Educational DP Contest

F

N = |s|, M = |t|
dp[ i ][ j ] := max( s[0,i) , t[0,j) の LCS(最長共通部分列) )
dp[ i ][ j ] = max( dp[ i-1 ][ j ], dp[ i ][ j-1 ], dp[ i-1 ][ j-1 ]+ (s[ i-1 ] == t[ j-1 ] ? 1 : 0) )

復元は dp[ N ][ M ] からスタートして ans = (空文字列)とし,
今 dp[ i ][ j ] を見ているとして
if s[ i-1 ] == t[ j-1 ] ans += s[ i-1 ]
else ( i-1, j-1 ), ( i-1, j ), ( i, j-1 ) のうち dpが等しい所に遷移.
i-1 < 0 or j-1 < 0 になったら ans を reverseして終了.
dp[ i-1 ][ j-1 ] + 1 == dp[ i ][ j ] でも s[ i-1 ] == t[ j-1 ] とは限らないので注意 (他の所から遷移してきたかもしれない)
O(NM).

Submission #3940676 - Educational DP Contest

G

dp[ u ] := max( uに至るパスの総長 )
トポロジカルソートをしてその順に
dp[ u ] = max( dp[ u ], dp[ v ] + 1 ) if v->u のパスが存在
さすがに配るDPの方が自然な気がする.
O(N).

Submission #3941322 - Educational DP Contest

H

dp[ i ][ j ] := sum( ( i, j ) に至る経路 ) dp[ 1 ][ 1 ] = 1, ans は dp[ H ][ W ]
if ( i, j ) が壁でない dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i ][ j-1 ]
else dp[ i ][ j ] = 0
O(HW).

Submission #3941908 - Educational DP Contest

I

dp[ i ][ j ] := prob( i 枚目まで投げて j 回表)
dp[ i ][ j ] = p * dp[ i-1 ][ j-1 ] + (1-p) * dp[ i-1 ][ j ]
dp[ 0 ][ 0 ] = 1
ans = sum{ i > floor(N/2) } ( dp[ N ][ i ] )
テストケース,結構誤差とかに気を使いそう.(こどふぉだとmodでやるよね)
O(N2).

Submission #3942299 - Educational DP Contest

J

dp( i, j, k ) := ( 寿司が1,2,3個乗った皿が i, j, k 枚あるまでの期待値 )
次に1,2,3,0個乗った皿をとる確率をp,q,r,sとすると
p = i / N, q = j / N, r = k / N, s = 1 - ( p + q + r )
p,q,r,s それぞれの確率で,その後に何回かかるかの期待値は
dp( i-1,j,k ), dp( i+1,j-1,k ), dp( i,j+1,k-1 ), dp( i,j,k ) になり,
それぞれで必ず1回は試行が増加するので
dp( i, j, k ) = p * dp( i-1,j,k ) + q * dp( i+1,j-1,k ) + r * dp( i,j+1,k-1 ) + s * dp( i,j,k ) + 1
の式が成り立つ.
dp( i, j, k ) の項を移行してメモ化再帰で解く
一瞬ループがないか気になってしまうが, まあよく考えればないことがわかる
期待値漸化式は けんちょんさんのブログ

Submission #4704505 - Educational DP Contest

K

a_i は1回しか使えないのかと誤読していた.
dp[ i ][ j ] := ( i 個石が残っている, j = (先手番 ?) の時、値が1なら先手勝ち )
として再帰してやればいい.
O(K).

Submission #4095737 - Educational DP Contest

L

dp[ i ][ j ] := ( a[ i, j ) からゲームを始めた時の得点. j - i = N mod 2 なら先手番なのでmax, 後手番ならmin )

if 先手番 dp[ i ][ j ] = max( dp[ i-1 ][ j ] + a_i, dp[ i ][ j-1 ] + a_j )
else dp[ i ][ j ] = max( dp[ i-1 ][ j ] - a_i, dp[ i ][ j-1 ] - a_j )

O(N2).

区間DP/ゲームはメモ化がやりやすいね

Submission #3945707 - Educational DP Contest

M

dp[ i ][ j ] := sum( i 人までに j 個を配る )
dp[ i+1 ][ j + k ] += dp[ i ][ j ] ( 0 <= k <= a_i )
そのままやると O(NK2) でTLEなので imos法を使う.
(集めるDPなら累積和)
O(NK).

Submission #3946111 - Educational DP Contest

N

dp[ l ][ r ] := min( [ l, r ) スライムを合体させるコスト )
最後に [ l, x ) と [ x, r ) から各々できるスライムを合体させるとしたら,
各々は a[ l, x ) , a[ x, r ) なので
dp[ l ][ r ] = min_{ l < x < r} ( dp[ l ][ x ] + dp[ x ][ r ] + a[ l, x ) + a[ x, r ) )
aは累積和をとっておこう.
O(N3).

Submission #3947535 - Educational DP Contest

アルゴリズムイントロダクションに乗ってる連鎖行列積とほとんど一緒だなあと思った.
このスライドの44ページ目から.

O

dp[ i ][ s ] := ( i 人目までの男性をマッチングさせて, 女性集合 s が残っている )
dp[ i ][ s ] = sum_{ j in s } ( dp[ i-1 ][ s \ j ] )
O( N2 2N ).

Submission #3947997 - Educational DP Contest

P

0を勝手に根として,
dp[ u ][ i ] := sum( u 以下を塗り, u は i==1 ? 黒 : 白 とする塗り方 )
dp[ u ][ 0 ] = prod _ { v in child( u ) } ( dp[ v ][ 0 ] + dp[ v ][ 1 ] )
dp[ u ][ 1 ] = prod _ { v in child( u ) } ( dp[ v ][ 0 ] )
どちらも子がない場合は 1.
ans = dp[ 0 ][ 0 ] + dp[ 0 ][ 1 ]
O(N).

Submission #3948387 - Educational DP Contest

和と積がこっちゃになる人は和集合(Or),積集合(And)を考えるとわかりやすいかも

Q

そのまま式を立てると
dp[ i ][ j ] := max( 左から i 本目まで見て一番高い花が j 本目の時の美しさの総和 )
dp[ i+1 ][ i+1 ] = max _ { h j < h_i } ( dp[ i ][ j ] ) + a_i
dp[ i ]の列は1つの値しか更新しなくて良いことに気づくので1次元にしよう.
( ( i, k) -> ( i+1, l) , ( i, l ) -> ( i+1, m) のような更新があると1次元では困る )
すると dp[ i ] := max( 一番高い花が i 本目である時の美しさの総和 ) となる.
遷移は
dp[ i ] = max{ j < i, h _ j < h _ i }( dp[ j ] ) + a_i
左から更新していくと j < i は常に満たされるので h_j < h_i なるものの中から max をとってやれば良い.
これは h_i をDPのキーとして持ってやればSegmentTreeでできる.
h_i が大きいと座圧してやる必要があるけど,これは順列になっているのでそのままできる.
よってDPテーブルをSegmentTreeで作って,
dp[ k ] := max( 一番高い花の高さがk の美しさ )
dp[ k ] = max_{0 <= j < k} ( dp[ j ] )

O(N logN).

Submission #3948747 - Educational DP Contest

R

これ数理情報学の院試で見たやつだ
A = (隣接行列) として Ak _{i, j} = ( i -> j の総長 k のパスの本数 ) になる.
これ自体知ってても良さそうだけど
dp[ k ][ i ][ j ] := ( i -> j の総長 k のパスの本数 ) とすると制約見て行列積しかないねってなりそう.
O(N3 log K).

Submission #3948940 - Educational DP Contest

S

桁DP.
dp[ i ][ j ][ k ] := sum( 上から i 桁まで決めて数字の総和 mod D が j , k == 1 ならその桁まで K と等しい )
dp[ 0 ][ 0 ][ 1 ] = 1 から
dp[ i+1 ][ ( j + K[ i ] ) % D ][ 1 ] += dp[ i ][ j ][ 1 ]
for 0 <= d < K[ i ] : dp[ i+1 ][ ( j + d ) % D ][ 0 ] += dp[ i ][ j ][ 1 ]
for 0 <= d <= 9 : dp[ i+1 ][ ( j + d ) % D ][ 0 ] += dp[ i ][ j ][ 0 ]
と配っていく.
O( |K| D).

Submission #3949252 - Educational DP Contest

T

小さい順に挿入していくことを考えすぎてできなかった.

dp[ i ][ j ] := #( [0,i) の位置まで配って末尾より大きいものが j 個残っている状態 )
i + j <= N を満たす.
この時, 状態 ( i , j ) からの遷移を考える.
s[ i-1 ] = '<' の時,
j 個の置く数の候補があり dp[ i ][ j ] を dp[ i+1 ][ k ] ( 0 <= k < j ) に足し込めばいい.

'>' の時,
N-i-j 個の候補があり(末尾より小さい数), dp[ i ][ j ] を dp[ i+1 ][ k ] (j <= k < N-i )に足しこむ.

愚直 O(N3) 、 imos法を使うと O(N2) になる.

Submission #4385313 - Educational DP Contest

U

p[ s ] := ( 集合 s を全員同じグループにした時に得られる得点 ) を前計算し,
dp[ s ] = max( 集合 s を使った時の合計得点 )
漸化式は
dp[ s ] := max_{ t = subset( s ) } dp[ s \ t ] + p[ t ]

各 s に対して 2N 列挙して部分集合なら遷移みたいな実装をすると O(4N) になるが,
正しく部分集合を列挙すると s で立っているビット数を b として
sum_ { 0 <= b <= N } comb(N, b) 2b = 3N となる.
詳しくは こことか

Submission #3970446 - Educational DP Contest

V

いわゆる全方位木DPというやつ.
dp[ u ] := ( u以下の部分木で u を黒で塗る塗り方) として,
dfsで0を根として dpテーブルを埋める.
その後もう一回 dfsをしていく, この際呼び出し元 u から子 v を呼んだ際に
pval := ( 木全体からvを根とする部分木を除いた木で u を黒に塗る塗り方 ) を持っていく.
すると頂点 u に関する答えは PI( dp[ vの子 ] + 1 ) * ( pval + 1) になる (PIは積)
後は v から その子に pvalを持って伝播させていけばいい.
これは累積和の要領で [ 0,i ) の積, [ i, sz(vの子) ) の積を持っておけば,
i 番目の子に関して pval = PI _ [ 0, i ) * PI _ [i+1, sz) で計算できる.

木と計算量 後編 〜全方位木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

Submission #4387140 - Educational DP Contest

W

やっと解説ACした. 要復習.

区間の操作関連でDPするときに,区間が含まれたときではなくその終点で操作を行う,みたいなやつ.
この解説がわかりやすすぎて書くことない.

Submission #5033754 - Educational DP Contest

X

まず荷物の置き方について, 上から Xの荷物, (w_1,s_1) , (w_2,s_2) と置くことを考える.
この時満たすべき条件は
X <= s_1 and X + w_1 <= s_2
<=> X <= min(s_1 , s_2 - w_1 )
これを swapすると X <= min( s_2 , s_1 - w_2) .
これが上における荷物の上限ということになる.
w_1 を上に置きたい時 min( s_1 , s_2 - w_1 ) >= min( s_2 , s_1 - w_2) .. (1) であればいい.
(1) <=> s_1 >= min( s_2, s_1 - w_2 ) (2) かつ s_2 - w_1 >= min( s_2, s_1 - w_2) (3) となる.
(2) は s_1 >= s_1 - w_2 から必ず満たす.
(3)は s_2 - w_1 >= s_2 が成り立つことはないため s_2 - w_1 >= s_1 - w_2 と同値.
よって s_1 + w_1 <= s_2 + w_2 を得る. つまり { s_i + w_i } で並べていけばいい.

dp[ i ][ x ] := max( i 番目のブロックまでを考え,合計の重さ x の時の価値)
とすれば
dp[ i+1 ][ x ] = max( dp[ i ][ x ], ( x-w_i <= s_i ? dp[ i ][ x - w_i ] + v_i : -INF) )

重さは最悪ケースの max( w ) + max( s ) 程度を考えればOK.
( max( w ) の上に max( s ) が乗っている )

Submission #4386153 - Educational DP Contest

Y

数学でもそうだけど,こういうの大体余事象を数える.
この際 i 番目の点を初めて通ったという条件を入れると独立に数えられる.
{ (r_i, c_i) } に (H-1,W-1) を加えて pair の昇順sortし,
dp[ i ] := ( i 番目の点を初めて通るような ( r_i, c_i ) へのパスの数 ) とすれば,
dp[ i ] = f( r_i, c_i ) - sum _ { j, r_j <= r_i かつ c_j <= c_i } ( dp[ j ] * f(r_i - r_j, c_i - c_j ) )
ただし f( r , c) = {r+c} C {r} これ身に付けたい.

Submission #4384588 - Educational DP Contest

Z

dp[ i ] = min{0 <= j < i } (dp[ j ] + (h[ i ] - h[ j ])2 + C )
愚直O(N2)だがConvexHullTrickを使うとO(N)になる.
(右辺) = min{ 0 <= j < i }( -2 h[ j ] * h[ i ] + ( dp[ j ] + h[ j ]^2 ) )+ ( h[ i ]^2 + C )
で左の min の部分が求められればいいが, これは h[ i ] を x とみなして CHTを適用すれば求められる.
dp[ i ] を求めた後は 直線 -2 h[ i ] * x + ( dp[ i ] + h[ i ]^2 ) をCHTの直線群に追加する.
-2h[ i ] は単調増加するのでこれは可能である.

Submission #4707883 - Educational DP Contest