TopCoder SRM 603 Div1 Easy MaxMinTreeGame

せっかくSRM602が好調だったのに0ptで吹っ飛んだ。
http://community.topcoder.com/stat?c=problem_statement&pm=12946

問題

木の形をしたグラフが与えられる。
各頂点にはスコアが振られている。

ここで、2人で交互にターンを行うゲームをする。
各ターンでは、残されたグラフについて1つ辺を選択して切断し、2つのグラフのうち片方を選択して残すことができる。
残グラフが頂点１つになるとゲームは終了である。

先手は残りの頂点を最大化しようとし、後手は最小化しようとする。
両者が最善手を取ったときどのスコアに落ち着くか示せ。

解答

本番ではダメ元で状態をbitmapで表現して探索したけど、案の定TLEでアウト。

ちなみに解答は、「辺が1個しかない点のうち最大スコアのものを先手が残し、それでゲーム終了」である。
本番その可能性も考えたけど、直感を信じ切れず全探索に走ったのが失敗だった。

辺が2個以上あるより高スコアの頂点を残すことがなぜできないかを考える。
先手にしろ後手にしろ、より望ましいスコアを持つ頂点が辺2個以上持っていたとする。
この頂点を最後に残すには全ての辺を消すために自分のターンが2ターン以上かかるが、そこまでの過程で相手がその頂点を先に切り離すことができるため、2辺以上の点を残すことはできない。

上記推論を繰り返すと、両者が互いに２辺以上の点を残すことができないため、結局先手が１辺しかつながらない点のうち最高スコアの点を残すのが最適手となる。

class MaxMinTreeGame {
	public:
	int findend(vector <int> edges, vector <int> costs) {
		int e[51];
		int i,x,y;
		int N=costs.size();
		
		ZERO(e);
		FOR(i,N-1) {
			e[i+1]++;
			e[edges[i]]++;
		}
		int ma=0;
		FOR(x,N) if(e[x]==1) ma=max(ma,costs[x]);
		return ma;
		
	}
};

まとめ

そういえば以前もNimじゃないEasyの２人ゲーを全探索して落としたことがある。
前回も今回も全探索じゃTLEになることはわかりきっているのに…。
証明が出来ればベストだが、時間内に証明までするのも大変だし直感で解答しても良いのかもしれない…。