SRM 674 div1 easy:VampireTree

SRM 674 は不参加です。まだ easy しか見てないですが easy は早解き出来そうな雰囲気だったので出たかったなぁ。

問題

TopCoder Statistics - Problem Statement

解法

まず, num[i] は各頂点 i の次数を表していることに気が付きます。
与えられたグラフが木になることを考えると, すべての頂点の次数の和は (辺の数)*2 = 2n-2 (n は頂点数) とならなければなりません。こうなっていなければ, -1 を返します。

そうでない場合は実は必ずグラフが構成できます。
以下のグラフを見てみます。

赤い頂点は, 次数が 1 でない点です。次数が 1 でない点を一直線につなげて, 次数 1 の点をその周りにくっつける, という戦略でグラフを作れば, 必ずグラフを構成できます。

また, このようにグラフを作ると, 直径を最大化出来ることにも気づきます。この理由をざっくり言うと, 次数が 1 のものでは頂点を媒介して距離を稼ぐことは出来ないので, 距離を稼ぐためには次数が非 1 の頂点で行うしか無いからです。

つまり, 次(数が 1 でない頂点の数) + 1 が最大の直径ということになります。

class VampireTree {
public:
    int maxDistance(vector <int> num) {
        int sum = 0, cnt = 0, n = num.size();
        for (int el : num) {
            sum += el;
            if (el != 1) cnt++;
        }
        if (sum != 2*n-2) return -1;
        return cnt+1;
    }
};

どうでもいいですが V から始まるクラスの名前, SRM では珍しい気がする(Z では ZigZag がすごく印象に残ってるけどこっちも少ない)。