torus711 のアレ

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

TopCoder SRM 603, Division 1, Level 1 : MaxMinTreeGame

概要

 木(グラフ的な意味で)を使った、次のような二人ゲームをする。

  • 各頂点には重みが付いている
  • 各プレイヤーは交互に動く
  • 各ターンでは、そのプレイヤーが任意の枝を選んでグラフを分割する
  • 分割されたグラフの内、どちらを次に残すかはそのプレイヤーが任意に決められる
  • 最後に残った頂点の重みがゲームの結果

 各プレイヤーの目標はそれぞれ、

  • 先攻のプレイヤーは結果の最大化を目指す
  • 後攻のプレイヤーは結果の最小化を目指す

である。お互いが最善を尽くしたときの結果を求めよ。

解法

 まず、先攻のプレイヤーは葉ノードに繋がる辺を切ることで、一ターンでゲームを終わらせることができます。従って、先攻の利益として葉ノードの内の最大コストは保証されます。あとは、葉ノード以外が解にならないことを示せれば、葉ノード中の最大コストを返すだけで解けることを示せます。
 葉ではないノードに全ての葉より大きいコストの頂点があるとします。先攻がゲームを終わらせずに後攻のターンになったとすると、今度は後攻のプレイヤーが葉ノードを一つだけ残してゲームを終わらせる事ができます。葉ノードは必ず二つ以上あるため、先攻の動きに関わらず初期状態で葉だったノードが一つ以上葉として残っています。従って、残る頂点のコストは着目している頂点(コストの大きい葉ではない頂点)のコスト以下になります。従って、先攻のプレイヤーは狙ったノードを結果とすることができません。後攻についても同様に考えると、お互いに葉ではないノードを狙おうおとすると相手に邪魔されてしまいます。
 結局、先攻は最初のターンで利確した方が得ということになります。ということで、先程の「葉ノード中の最大コストを返す」という解法で解くことができます。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class MaxMinTreeGame
{
public:
	int findend( vector <int> edges, vector <int> costs )
	{
		const int N = costs.size();

		VI degrees( N, 0 );

		REP( i, 0, N - 1 )
		{
			degrees[ i + 1 ]++;
			degrees[ edges[i] ]++;
		}

		int res = 0;
		REP( i, 0, N )
		{
			if ( degrees[i] == 1 )
			{
				res = max( res, costs[i] );
			}
		}
		return res;
	}
};