torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, Single Round Match 666, Division 1, Level 1 : WalkOverATree

問題概要

 $N$ 頂点の木があって,各頂点は $0$ から $N - 1$ で番号付けられている.木の情報は配列 $\mathit{ parent }$ で与えられ,有効な $i$ について,頂点 $i + 1$ と $\mathit{ parent }_i$ の間に辺があることを表す.
 この木の上で移動することを考える.あるノードからの一回の移動では,そのノードに隣接する頂点に移動することができる.
 頂点 $0$ から始めて,$L$ 回以内の移動で到達できる頂点の数を求めよ(始点も含む)(重複は数えない).

  • $1 \leq N \leq 50$
  • $0 \leq \mathit{ parent }_i \leq i$
  • $1 \leq L \leq 100$

解法

 同じ辺を(向きを考慮せず)3 回以上通る場合は無駄なので考えないことにします.
 まずは簡単な場合として,始点に帰ってくる場合について考えてみます.この場合,新たに訪問する頂点 1 つあたり,往復分のコストが発生します.つまり,新たに訪問する頂点を 1 つ増やす度,$2$ のコストがかかります.
 もちろん,わざわざ始点に帰ってくるのは無駄なので,最適な移動(の 1 つ)では始点とは異なる点で終了します.この点を終点と呼ぶことにすると,始点から終点へのパスを考えることができます.このパス上を移動しながら,ときどき脇道に逸れて訪問済み頂点数を増やしてから,またこのパスに戻ってきて先に進む,という移動方法を実行できます.このとき,パス上の頂点を訪問済みにするコストは(復路が無いので) $1$ となります.
 では,終点の選び方はどうするのがよいでしょうか.辺を高々 1 度しか使わないパスは 1 本しか引けません.また,パス上の頂点を訪問済みにするコストは,そうでない頂点を訪問済みにするコストより安いので,できるだけ多くの頂点をパスに含めるのが最適となります.従って,始点から最も遠い頂点を終点に選ぶのが最適です.
 終点を決めたとき,新たに訪問可能な頂点数は

  1. パスに含まれる始点以外の頂点は訪問確定なので,その分を数えて,残り移動回数をパスの長さ分減らす
  2. 残りのコスト目一杯使って残りの頂点に訪問する(コスト $2$ あたり 1 つ増やせる)

という具合に計算できます.距離 $L$ より遠いところに行ったり,$N$ より多くの頂点に訪問したりすることはできないのでその点には注意です.
 この解法は,始点から最も遠い点を求める部分以外は全て定数時間の処理で,最遠点を求める部分に最も時間がかかります.各 $i$ について $0 \leq \mathit{ parent }_i \leq i$ であることを利用すると,最遠点はちょっとした DP で $O( N )$ 時間で求められます.従って全体でも $O( N )$ 時間となります.

コード

using VI = vector< int >;

#define SZ( v ) ( (int)( v ).size() )

class WalkOverATree
{
public:
	int maxNodesVisited( vector <int> parent, int L )
	{
		int N = SZ( parent ) + 1;

		VI dp( N );
		for ( int i = N - 2; 0 <= i; --i )
		{
			dp[ parent[i] ] = max( dp[ parent[i] ], dp[ i + 1 ] + 1 );
		}

		const int d = dp[0];
		int res = 1;
		res += min( L, d );
		L -= res - 1;
		res += min( N - res, L / 2 );
		return res;
	}

};