topcoder SRM 666 WalkOverATree

頂点数N (1 <= N <= 50) の木がある。スタート地点が決められており、辺の上を移動できる回数L (1 <= L <= 100) が与えられたとき、最適な動き方をすれば、(重複を許さないで) 最大で何個の頂点に行くことができるか?

O(LN3) よりは小さい解法

頂点v以下にある部分木に、残り移動回数lで最適な動き方をするときに行ける頂点数をbestMove(v,l)としてDPする。

今、下図の青色の頂点にいるとする。青色の頂点は3つの子を持つので、以下の3つの戦略が取れる。

  • 左と中央の子の下にある部分木で適当に寄り道をしてから、青色の頂点に戻って赤色の頂点に行く
  • 左と右の子の下にある部分木で適当に寄り道をしてから、青色の頂点に戻って赤色の頂点に行く
  • 中央と右の子の下にある部分木で適当に寄り道をしてから、青色の頂点に戻って赤色の頂点に行く

f:id:kujira16:20150827093817p:plain

部分木がM個の頂点を持つとき、0, 2*1, 2*2, ..., 2*Mの移動回数を消費して0, 1, 2, ..., M個の頂点に寄り道することができる。

O(N) 解法

最適な動き方をした時に、最後にいる頂点を決めたとする。例として、下の図ではスタートの頂点が青色、最後にいる頂点が赤色である。

f:id:kujira16:20150827100220p:plain

赤色の頂点の頂点からの距離をdepth[v]とする。青から赤の移動でdepth[v]の移動回数を使う間に、残りのL-depth[v]の移動回数を活用して寄り道をすればよい。

(加筆の予定は未定です)