torus711 のアレ

主に競技プログラミングの問題について書きます

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

問題概要

 $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 でなくてもよい