2017/10/08の精進

いまだ上手い(バグらせない)木DPの書き方がわかってない

プロの実装を学んだりするのも重要かもしれない

・yukicoder No.196 典型DP(1)

dp[i][j]=subtree(i)のうちj個の頂点を黒く塗る方法が何通りか

とすると頂点iを黒く塗るときはその下も全て黒く塗るのでいいとして、頂点iを白く塗るときは子にj個の黒い頂点を振り分けることになる

DFSの中で(i-1番目までのsubtreeの頂点数の和)×(i番目のsubtreeの頂点数)のループを回していくとO(N^3)っぽく見えるけど実はO(N^2)で動くという話があってそれ

yukicoder No.196 典型DP (1) - mayoko’s diary

 貰うDP書きがちなんだけど、配るDPやっといて更新する方法の方が汎用性高い?

Codeforces #419 Div1C Karen and Supermarket

クーポンaを使わないとクーポンbが使えないというとき辺a→bを張ると木が出来る

dp[i][j][k]=subtree(i)からj個の頂点を選ぶときの価格の最小値(k=0のとき頂点iでクーポンを使わない k=1のとき頂点iでクーポンを使う)

というDPを前問と同じようにO(N^2)におとしてやってやる

・square869120Contest #4 D Driving on a Tree

†全方位木DP†について - ei1333の日記

うしさんの†全方位木DP†の説明を読んだので練習としてやった

根を適当に決めた場合、dp[v]=今頂点vにいるとき停止するまでの動く回数の期待値

とするとこれは容易に計算できる(この記事も参考になる→期待値と条件付確率 - math314のブログ

次に根を動かしていくのだけど、親から伝播させる値は(Σ(1+dp[つながっている頂点])-(1+dp[移動する頂点]))/(つながっている頂点数-1)で求まるので簡単

 ・yukicoder No.260 世界のなんとか3

桁DP入門 - pekempeyのブログ

これを読んだのでといた(そのまんま)

 ・TDPC I イウィ

これは区間DPの練習 嘘アルゴリズムを書いたりバグらせたり迷走してつらい

dp[l][r]=[l,r)を取りのぞけるか

として短い区間から見ていく

[l,r)が取りのぞけるのはあるm∈[l,r)があって

s[l]=i s[m]=w s[r-1]=iであって[l+1,m)と[m+1,r)が取りのぞける

または

[l,m) [m,r)が取りのぞける

のどちらかのとき

あとは前から貪欲に取っていく