SRM675 Div1 Easy "TreeAndPathLength3"
考えた解法
0と1をとりあえず繋げる。
他の頂点は0または1にだけ繋げることを考えると、長さ3のシンプルパスの数は0に繋げた頂点の数 * 1に繋げた頂点の数になる。
9991とかの大きめの素数はこれだけだと丁度にならないので、0に繋げた頂点のどれかに直列に繋げて補完する。
例えばs = 19のとき、0に3つ、1に5つ繋げて3 * 5 = 15 残り4。あとは0に繋がっている頂点に直列に2つ繋げて3 + 1 = 4追加する。
イメージは以下のような感じ
事後
ソースコード
class TreeAndPathLength3 { public: vector<int> construct(int s) { // とりあえず0と1を繋げる vector<int> ans; ans.push_back(0); ans.push_back(1); for (int on0 = 1; on0 <= 200; on0++) { for (int on1 = 1; on1 <= 200; on1++) { int rem = s - on0 * on1; if (rem == 0 || (on0 <= rem && rem - on0 + 1 <= 500 - (on0 + on1 + 2))) { int cur = 2; // 1に繋げまくる for (int i = 0; i < on1; i++) { ans.push_back(1); ans.push_back(cur++); } // 0に繋げまくる for (int i = 0; i < on0; i++) { ans.push_back(0); ans.push_back(cur++); } // 残りを直列に繋げまくる rem = rem - on0 + 1; cur--; for (int i = 0; i < rem; i++) { ans.push_back(cur); ans.push_back(++cur); } return ans; } } } return ans; } };