きままにものづくりスマートフォン用の表示で見るきままにものづくり日々の気付いたことなんかを書いてます。この広告は、90日以上更新していないブログに表示しています。2014-12-19SRM622Div1Medium問題ノード数Nのツリーが与えられる。ツリー内部のノード同士の距離がDを超えないように、K個のサブツリーを構築する。解法メモ化と再帰を用いて解く。d)はノードxをルートとした時の最小のサブツリーの数を返す。xはノードの番号、dは進むことが可能な深さを示す。ノードxをルートとした時のサブツリーは以下の条件を満たす。xからリーフまでの最長距離がD以下サブツリー内のノード内の距離がD以下ノードxの子であるノードyを選び、サブツリーの最大深さをMと仮定する。M-dy)でサブツリーの数を探索する。dyはxからyまでの距離を示す。次に、ノードxの子であるノードzがノードyを含んでサブツリーを構築できるかを調べる。この時、満たす必要がある条件はxからリーフまでの最長距離がM以下サブツリー内のノード内の距離がD以下ひとつめは、最大深さをMと仮定しているからである。これらの条件を式にするととなる。