Hatena::Grouptopcoder

(iwi) { 反省します

TopCoder: [[iwi]] / Twitter: @iwiwi

 | 

2012-04-28

二乗の木 DP

02:53 | 二乗の木 DP - (iwi) { 反省します を含むブックマーク はてなブックマーク - 二乗の木 DP - (iwi) { 反省します 二乗の木 DP - (iwi) { 反省します のブックマークコメント

http://codeforces.com/contest/178/problem/F3

コレ面白かった.多分,O(n^3) の DP 解を気をつけて実装しているつもりで,気づいたら O(n^2) になっていた,という人が結構居るのでは.実は常識?


詳細は省くが,木の DP で,左の部分木のサイズが l,右の部分木のサイズが r で,計算量の漸化式が,

T(l + r) = T(l) + T(r) + l×r

と書けるとする.これは,各ノードで毎回サイズの 2 乗という感じなので,T(n) = O(n^3) かなと思ってしまう.

でもよく考えると,(l + r)^2 = l^2 + 2lr + r^2 なので,T(n) = O(n^2).


この漸化式は,例えば木に何かを k 個配置する最適な置き方を決めよう,とかで,木の各ノードで分け方試すみたいな感じでDPしようとすると自然に現われる.

うむ,やっぱあまりに汎用性が高いので僕が知らなかっただけで常識なのではないかと思い始めた.

JessicaJessica2012/07/10 01:54This makes everything so completely pialness.

bxqrzgbbxqrzgb2012/07/10 21:55bCIKEA , [url=http://wrruysbmvqht.com/]wrruysbmvqht[/url], [link=http://ktigynhtdfts.com/]ktigynhtdfts[/link], http://zgktnqoadufn.com/

snemcxwmypusnemcxwmypu2012/07/12 17:46PTwMNC , [url=http://rshasuziethd.com/]rshasuziethd[/url], [link=http://msqqgxgewqly.com/]msqqgxgewqly[/link], http://mklceoqvivco.com/

 |