SRM603 Div1 Easy "MaxMinTreeGame"
問題
TopCoder Statistics - Problem Statement
訳
MasMinTreeGameは二人用のゲームである。このゲームはツリーを使う。そのツリーはN個の0~N-1と番号が振られたノードがある。それぞれのノードは整数のコストがある。
ターン制でありプレイヤーは順番が交互に回ってくる。ターンが来たプレイヤーは1つのエッジを選び、それを消す。2つに分かれたツリーのうち、片方を残し、もう片方を消す。
ただ1つのノードとなった段階でゲームが終了する。そのノードのコストがゲームの結果となる。先行のプレイヤーは結果を最大化したい。後攻のプレイヤーは結果を最小化したい。
あなたはゲーム中のツリー構造を表すint[] edgesが与えられる。ノードi+1はedges[i]のノードとエッジで繋がっていることを表す。
2人のプレイヤーが最善を尽くしたとして、ゲームの結果を返せ。
制約
2 <=N <= 50
0 <= コスト <= 10^9
考えたこと
現在のターンで終わらせるには、端っこノード(1つの辺としか繋がっていないノード)を選ぶしかない。端っこノードが{1, 2, 3}だったとする。先行としては、3のノードのエッジを消して、結果を3としてゲームを終わらせるか、さらなるコストアップを計るかだ。
さらなるコストアップを計る場合、後攻にターンを回すことになる。さらにそのとき、この3つのノードのうちどれか1つは必ず端っこノードとして残る。1や2が残ってしまってはそれを選んでゲームを終わらせてくるかもしれない。例え端っこノードが{10000, 3, 10000}とかなっても3で終わらせてくるだろう。
つまり後攻にターンを渡すのは意味がない。よって端っこノードの最大コストを選んでゲーム終了となる。
ソースコード
class MaxMinTreeGame { public: int findend(vector <int> edges, vector <int> costs) { int n = costs.size(); bool G[55][55]; memset(G, false, sizeof(G)); for (int i = 0; i < edges.size(); i++) { int s = i + 1; int t = edges[i]; G[s][t] = G[t][s] = true; } int res = 0; for (int i = 0; i < n; i++) { int c = 0; for (int j = 0; j < n; j++) { if (G[i][j]) c++; } if (c == 1) res = max(res, costs[i]); } return res; } };