TopCoder SRM 670, Division 1, Level 2 ( Division 2, Level 3 ) : Treestrat

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13990&rd=16550

問題概要

　$N$ 頂点の木と 2 種類のトークンを使った 2 人ゲームをする．プレイヤーを A, B として，A は赤いトークンを，B は青いトークンを使う．
　木の頂点は $0$ から $N - 1$ で番号付けられている．ゲームの初期状態は 3 つの配列 $\mathit{ tree }$, $A$, $B$ により与えられる．$\mathit{ tree }$ は木の形を表し，$i$ ( $1 \leq i \leq N - 1$ ) について，2 頂点 $i$, $\mathit{ tree }_{ i - 1 }$ 間に辺があることを表す．$A$ は赤いトークンの初期位置を，$B$ は青いトークンの初期位置を表す（ $a \in A$ なる頂点 $a$ に赤いトークンがある．$B$ と青いトークンについても同様）．
　ゲームは Round と呼ばれる工程の繰り返しからなる．1 回のラウンドは，

1. A が赤いトークンをいくつか選び，それぞれ隣接する頂点に移動させる
2. B が青いトークンをいくつか選び，それぞれ隣接する頂点に移動させる

という 2 つのフェーズからなる．
　Round 終了後に，2 種類のトークンが存在する頂点が 1 つでもあれば，B の勝利となる．
　B はできるだけ少ない Round 数で勝ちたいと思っていて，A はできるだけ多くの Round をプレイしたいと思っている．両者が最善を尽くすとき，プレイされる Round 数を求めよ．B が有限の Round 数で勝利できることは保証されている．

• $2 \leq N \leq 50$

解法

　B の目的及び B が後手であることを考えると，A が B から逃げるゲームです．また，B は A の動きを見てから動けるので，赤いトークンは青いトークンと「すれ違う」ことはできません．
　以上を踏まえ，B が捕まえようとする赤いトークンを 1 つ固定したとします．A 目線で考えると，このトークンが捕まらずに動ける範囲は，全ての青いトークンより早く到達できる頂点だけであることが分かります．安全に到達可能な頂点の内，青いトークンの到達が最も遅い頂点に留まることで，その到達時刻まで生き延びることができます．
　B 目線で考えると，狙うトークンを決めれば互いの最適戦略も決まって Round 数が求まるので，狙うトークンを全通り試せば，最も早く捕まえられるトークンが分かります．

　トークンから距離を求める為に，$O( N )$ 回の BFS が走ります*1．BFS は木の上では $O( N )$ 時間で実行でき，BFS 後の集計も $O( N )$ 時間なので，全体では $O( N^2 )$ 時間となります．

コード

using VI = vector< int >;
using VVI = vector< vector< int > >;
template < typename T = int > using LIM = numeric_limits< T >;

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) begin( c ), end( c )

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

constexpr int INF = LIM<>::max() / 2;

class Treestrat
{
public:
	int roundcnt( vector <int> tree, vector <int> A, vector <int> B )
	{
		const int N = SZ( tree ) + 1;

		VVI G( N );
		REP( u, 1, N )
		{
			const int v = tree[ u - 1 ];
			G[u].PB( v );
			G[v].PB( u );
		}

		const VI from_b = bfs( G, B );

		int res = INF;
		FOR( a, A )
		{
			const VI from_a = bfs( G, { a } );

			int tmp = 0;
			REP( i, N )
			{
				if ( from_a[i] < from_b[i] )
				{
					tmp = max( tmp, from_b[i] );
				}
			}

			res = min( res, tmp );
		}

		return res;
	}

	VI bfs( const VVI &G, const VI &starts )
	{
		const int N = SZ( G );

		VI distances( N, INF );
		queue< int > que;
		FOR( s, starts )
		{
			distances[s] = 0;
			que.push( s );
		}

		while ( !que.empty() )
		{
			const int u = que.front();
			que.pop();

			FOR( v, G[u] )
			{
				if ( distances[u] + 1 < distances[v] )
				{
					distances[v] = distances[u] + 1;
					que.push( v );
				}
			}
		}

		return distances;
	}
};

*1:別に BFS でなくてもよい