SRM 603 DIV1 Easy - MaxMinTreeGame

問題


http://community.topcoder.com/stat?c=problem_statement&pm=12946&rd=15836

有向グラフが与えられる。
各ノードについてはコストを持つ。

2人のプレイヤーがゲームを行い、各ターンごとにグラフを2つに分割し、
好きな方の1つを消すことができる。

最初のプレイヤーはできるだけ最後に残るノードのコストを大きくしたく、
2人目のプレイヤーはできるだけ小さくしたい。

このとき、最後に残るノードの最大コストを求める。

解き方


2人ゲームなので必勝法を考察する。

今回は間にあるノードを残したくても、相手のターンで必ず消されてしまう。
逆に端にあるノードは必ず残すことができる。

よって、端にあるノードのうち最大のものが答えになる。

コード


class MaxMinTreeGame {

public: int findend(vector<int> edges, vector<int> costs) {
int n=costs.size();
int d[n][n];

memset(d,0,sizeof(d));
FORE(i,0,edges.size()){
d[edges[i]][i+1]=1;
d[i+1][edges[i]]=1;
}

int ret=0;
FORE(i,0,n){
int cnt=0;
FORE(j,0,n)if(d[i][j])cnt++;
if(cnt<=1)ret=max(ret,costs[i]);
}

return ret;
}

};
このエントリーをはてなブックマークに追加