頂点数N (1 <= N <= 50) の木がある。スタート地点が決められており、辺の上を移動できる回数L (1 <= L <= 100) が与えられたとき、最適な動き方をすれば、(重複を許さないで) 最大で何個の頂点に行くことができるか?
O(LN3) よりは小さい解法
頂点v
以下にある部分木に、残り移動回数l
で最適な動き方をするときに行ける頂点数をbestMove(v,l)
としてDPする。
今、下図の青色の頂点にいるとする。青色の頂点は3つの子を持つので、以下の3つの戦略が取れる。
- 左と中央の子の下にある部分木で適当に寄り道をしてから、青色の頂点に戻って赤色の頂点に行く
- 左と右の子の下にある部分木で適当に寄り道をしてから、青色の頂点に戻って赤色の頂点に行く
- 中央と右の子の下にある部分木で適当に寄り道をしてから、青色の頂点に戻って赤色の頂点に行く
部分木がM個の頂点を持つとき、0, 2*1, 2*2, ..., 2*Mの移動回数を消費して0, 1, 2, ..., M個の頂点に寄り道することができる。
O(N) 解法
最適な動き方をした時に、最後にいる頂点を決めたとする。例として、下の図ではスタートの頂点が青色、最後にいる頂点が赤色である。
赤色の頂点の頂点からの距離をdepth[v]
とする。青から赤の移動でdepth[v]
の移動回数を使う間に、残りのL-depth[v]
の移動回数を活用して寄り道をすればよい。
(加筆の予定は未定です)