WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};