SRM721 Lv2 : GraphAndPairs
作成日：2017.09.29
最終更新日：2017.09.29
問題概要
距離がちょうど$d$である2つの異なる頂点の組がちょうど$k$個ある単純なグラフ(連結でなくても良い)を1つ求めよ。
但し、頂点の数$n$は$3 \leq n \leq 1000$、辺の数$m$は$2 \leq m \leq 1000$を満たしていなければならない。
制約
$2 \leq d \leq 50$
$1 \leq k \leq 5 \times 10^4$
考え方
距離が$d$である頂点の組を1つ作るには頂点を$(d+1)$個鎖状につなげば良い。
これに頂点をつなげることで条件を満たす組を増やすことを考える。
できるだけ少ない頂点で増やすためには、端から2つ目の頂点に新たな頂点をつなげば良い。
$d > 2$の時には端から2つ目の頂点は2つある。
その2つの頂点のみとつながる頂点の数をそれぞれ$x,y$とすると、条件を満たす組は$(x \times y)$個ある。
$x \times y$が一定の時、$x+y$を最小にするには$x$と$y$が近い値であるのが良い。
そこで$x \times y$が$k$を超えないように$x$と$y$をできるだけ均等に増やしていくことにする。
これ以上増やせなくなったら$k$を$x \times y$だけ減らして、$k \neq 0$である限り問題を解き続ける。
一方$d = 2$の時には端から2つ目の頂点は1つだけである。
そこにつながる頂点の数を$x$とすると、条件を満たす組は$\frac{x(x-1)}{2}$個ある。
$d > 2$の時と同様にこの値が$k$を超えないように$x$を増やした後、$k$を$\frac{x(x-1)}{2}$だけ減らして$k \neq 0$である限り問題を解き続ける。
あとは以上のような手順で構築されるグラフの頂点や辺の数が条件を満たすことを確かめれば良い。
下限は$d=2$、$k=1$の時に満たしていることから常に満たされる。
また一つの連結成分を作るために必要な頂点の数は$(2\sqrt{k}+d)$個ほどであり、その結果$k$は$\sqrt{k}$ほどになるので上限も満たされることが予想される。
実際にコードを書いた後に$d,k$が大きい場合に確かめてみると大丈夫であることが分かる。
ソースコード
マクロ等はこちら
class GraphAndPairs {
public:
vector<int> construct(int d, int k) {
vector<int> ans;
ans.PB(1000);
int no = 0;
if(d == 2){
while(k > 0){
int p = no;
int co = 1;
while(co * (co-1) / 2 <= k){
ans.PB(p);
ans.PB(p+co);
++co;
}
k -= (co-1) * (co-2) / 2;
no += co;
}
} else {
while(k > 0){
int p = no;
int q = no+d-2;
repp(i,1,d-1){
ans.PB(p+i-1);
ans.PB(p+i);
}
no += d-1;
int s = 1 , t = 1;
while(s * t <= k){
if((s+1) * (t+1) <= k) ++s;
++t;
}
--t;
repp(i,0,s){
ans.PB(p);
ans.PB(no);
++no;
}
repp(i,0,t){
ans.PB(q);
ans.PB(no);
++no;
}
k -= s*t;
}
}
return ans;
}
};解法まとめ
$k = 0$となるまで以下を繰り返す。
$d = 2$の時は$\frac{x(x-1)}{2} \leq k$となる最大の$x$を取ってきて、1つの頂点に$x$個頂点をつなげた連結成分を作る。
そして$k$を$\frac{x(x-1)}{2}$だけ減らす。(8-18行)
$d > 2$の時は$x^2 \leq k$となる最大の$x$を取り、その後$x \times y \leq k$となる最大の$y$を取る。
$(d-1)$個の頂点を鎖状につなげたものの両端の頂点にそれぞれ$x,y$個の頂点をつなげた連結成分を作る。
そして$k$を$x \times y$だけ減らす。(20-45行)