TopCoder SRM 721 Div1 Medium GraphAndPairs

今回解くのにかかった時間がEasy(failed) ＞ Medium ＞ Hardだったんだけどどういうこと…。
https://community.topcoder.com/stat?c=problem_statement&pm=14714

問題

整数D,Kが与えられる。
1000頂点以下・1000辺以下の無向グラフで、最短距離がDとなる頂点対がちょうどK個となるものを構築せよ。

解法

D==2の場合

(a+1)頂点の星形を作るとa*(a-1)/2個の頂点対ができる。
よって合計がK個となるようにそのような星形をいくつか作ろう。

D＞2の場合

(D-1)頂点を並べて長さ(D-2)のパスを作る。
両端にa,b個の点をつなげると、距離Dの対がa*bできる。
よってa+bがあまり大きくならないように、a*bの和がKとなる(a,b)の組をいくつか作ろう。

class GraphAndPairs {
	public:
	vector<int> hoge2(int K) {
		vector<int> R;
		R.push_back(0);
		int num=0;
		int i,j;
		while(K) {
			for(int i=1000;i>=1;i--) {
				if(i*(i-1)/2<=K) {
					FOR(j,i) R.push_back(num),R.push_back(num+1+j);
					num+=i+1;
					K-=i*(i-1)/2;
					break;
				}
			}
		}
		R[0]=num;
		return R;
		
	}
	
	vector <int> construct(int D, int K) {
		if(D==2) return hoge2(K);
		vector<int> R;
		R.push_back(0);
		int num=0;
		int i,j;
		while(K) {
			FOR(i,D-2) R.push_back(num+i),R.push_back(num+i+1);
			int LL=num;
			int RR=num+D-2;
			num+=D-1;
			
			for(int i=1000;i>=1;i--) {
				if(i*i<=K) {
					FOR(j,i) R.push_back(LL),R.push_back(num+j);
					FOR(j,i) R.push_back(RR),R.push_back(num+i+j);
					
					num+=2*i;
					K-=i*i;
					break;
				}
				if(i*(i-1)<=K) {
					FOR(j,i) R.push_back(LL),R.push_back(num+j);
					FOR(j,i-1) R.push_back(RR),R.push_back(num+i+j);
					
					num+=2*i-1;
					K-=i*(i-1);
					break;
				}
				
			}
		}
		R[0]=num;
		return R;
	}
}

まとめ

これ、連結を条件に付けた方が面白いんでないかな…。