概要
木(グラフ的な意味で)を使った、次のような二人ゲームをする。
- 各頂点には重みが付いている
- 各プレイヤーは交互に動く
- 各ターンでは、そのプレイヤーが任意の枝を選んでグラフを分割する
- 分割されたグラフの内、どちらを次に残すかはそのプレイヤーが任意に決められる
- 最後に残った頂点の重みがゲームの結果
各プレイヤーの目標はそれぞれ、
- 先攻のプレイヤーは結果の最大化を目指す
- 後攻のプレイヤーは結果の最小化を目指す
である。お互いが最善を尽くしたときの結果を求めよ。
解法
まず、先攻のプレイヤーは葉ノードに繋がる辺を切ることで、一ターンでゲームを終わらせることができます。従って、先攻の利益として葉ノードの内の最大コストは保証されます。あとは、葉ノード以外が解にならないことを示せれば、葉ノード中の最大コストを返すだけで解けることを示せます。
葉ではないノードに全ての葉より大きいコストの頂点があるとします。先攻がゲームを終わらせずに後攻のターンになったとすると、今度は後攻のプレイヤーが葉ノードを一つだけ残してゲームを終わらせる事ができます。葉ノードは必ず二つ以上あるため、先攻の動きに関わらず初期状態で葉だったノードが一つ以上葉として残っています。従って、残る頂点のコストは着目している頂点(コストの大きい葉ではない頂点)のコスト以下になります。従って、先攻のプレイヤーは狙ったノードを結果とすることができません。後攻についても同様に考えると、お互いに葉ではないノードを狙おうおとすると相手に邪魔されてしまいます。
結局、先攻は最初のターンで利確した方が得ということになります。ということで、先程の「葉ノード中の最大コストを返す」という解法で解くことができます。
コード
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; } };