きままにものづくり

日々の気付いたことなんかを書いてます。

SRM622Div1Medium

問題

ノード数Nのツリーが与えられる。ツリー内部のノード同士の距離がDを超えないように、K個のサブツリーを構築する。最小のKを求めよ。

解法

メモ化と再帰を用いて解く。f(x, d)はノードxをルートとした時の最小のサブツリーの数を返す。xはノードの番号、dは進むことが可能な深さを示す。ノードxをルートとした時のサブツリーは以下の条件を満たす。

  • xからリーフまでの最長距離がD以下
  • サブツリー内のノード内の距離がD以下

ノードxの子であるノードyを選び、サブツリーの最大深さをMと仮定する。ノードyに対してはf(y, M-dy)でサブツリーの数を探索する。dyはxからyまでの距離を示す。次に、ノードxの子であるノードzがノードyを含んでサブツリーを構築できるかを調べる。この時、満たす必要がある条件は

  • xからリーフまでの最長距離がM以下
  • サブツリー内のノード内の距離がD以下

ひとつめは、最大深さをMと仮定しているからである。
これらの条件を式にすると
 min(M, D-M)
となる。
ノードxからノードzまでの距離dzが以下の式を満たす場合は、
 dz \leq min(M, D-M)
f(z, r - dz)を探索する。rはmin(M, D-M)である。
Mについて全探索することで解を求めることができる。

計算量

全計算量: O(N^3D^2)
N:ノード数
D:maxDist-ノード間の最大距離

再帰の回数:O(ND)
再帰の中身:  O(N^2D)

コード