Topcoder SRM 721 Div1 Medium - GraphAndPairs
問題概要
整数d, kが与えられる。最短距離がdであるような頂点のペアがちょうどk個あるような無向グラフを構成せよ。ただしすべての辺の距離は1とし、辺・頂点とも最大で1000個までとする。
2 <= d <= 50
1 <= k <= 50000
解法
(D-1)個の頂点を一直線につないだグラフを考える。このグラフの両端にn個ずつ頂点をくっつけると両側の距離がちょうどdになるので、条件を満たすペアはn2個になる。このようなグラフを独立に何個も作っていくことにすれば、結局kを平方数の和で表す問題に帰着する。貪欲でやっても最大ケースで800個程度しか頂点を使わないので十分収まる。ただしd=2がコーナーケースで、ひとつの頂点を中心に他の点をくっつけていく形になるので、その場合の処理は分けて書く必要がある。
感想
なんか全然思いつかなかったです
コード (C++)
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for (int i=0;i<(n);i++) #define REP2(i,m,n) for (int i=m;i<(n);i++) typedef long long ll; class GraphAndPairs { public: vector<int> construct(int D, int K) { vector<int> ans; if (D == 2) { for (int n = 0; n < 1000 && K > 0; ++n) { int m = n; int s = 0; for (n = n + 1; n < 1000 && s <= K; ++n) { ans.push_back(m); ans.push_back(n); K -= s; s += 1; } } } else { for (int n = 0; n < 1000 && K > 0; ) { int m1 = n; int m2 = n + D - 2; for (n = n + 1; n <= m2; ++n) { ans.push_back(n - 1); ans.push_back(n); } int cnt; for (cnt = 1; n < 1000 && K - cnt * cnt >= 0; cnt += 1, n += 2) { ans.push_back(n); ans.push_back(m1); ans.push_back(n + 1); ans.push_back(m2); } cnt -= 1; K -= cnt * cnt; } } int mx = 0; for (auto a: ans) mx = max(mx, a); ans.push_back(mx + 1); reverse(ans.begin(), ans.end()); return ans; } };