SRM 675 div1 easy:TreeAndPathLength3
SRM 675 に参加しました。
easy まぁまぁの点数で出せたのにしょうもないミス…
なんか最近 med は計算量落とし問題が多くて雰囲気変わったなぁって思いますね。
解法
まず, 頂点 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; } };