SRM 675 div1 easy:TreeAndPathLength3

SRM 675 に参加しました。
easy まぁまぁの点数で出せたのにしょうもないミス…

なんか最近 med は計算量落とし問題が多くて雰囲気変わったなぁって思いますね。

問題

TopCoder Statistics - Problem Statement

解法

まず, 頂点 0 から 頂点を 2 つずつ生やします。下図のような感じですね(頂点 0 が 赤色)。

この「足」が n 個ある時, 長さ 3 のパスは n*(n-1) 個出来ます。
また, ここで足を構成するのが頂点 2 つでなく頂点 1 つにすると, 長さ 3 のパスは 1 つ増えます。よって, あとはパスが s に達する周りにバーっと頂点をつけていきましょう。

class TreeAndPathLength3 {
public:
    vector <int> construct(int s) {
        int n = 0;
        while (n*(n-1) <= s) n++;
        n--;
        int rest = s-n*(n-1);
        int cur = 1;
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            ans.push_back(0);
            ans.push_back(cur);
            ans.push_back(cur);
            ans.push_back(cur+1);
            cur += 2;
        }
        for (int i = 1; i <= rest; i++) {
            ans.push_back(i*2);
            ans.push_back(cur++);
        }
        return ans;
    }
};