kmjp's blog

競技プログラミング参加記です

TopCoder SRM 675 Div1 Easy TreeAndPathLength3

色んな解き方がありそうな問題。
https://community.topcoder.com/stat?c=problem_statement&pm=14089

問題

1~10000の範囲の整数sが与えられる。
500頂点以下からなる無向辺を用いた木で、長さ3のパスがs個あるようなものを構築せよ。

解法

∋-∈型の形状を作れば、長さ3のパスがO(頂点数^2)個あるような木が作れる。
ただ、これだけではsが合成数でない場合に対応できない。
いくつか解法があるようだが、自分は以下のようにした。

  • s≦497の場合、(s+3)個頂点を1列に並べれば良い。
  • s>497の場合
    • 以下のように、0-1-2-3と一列に並べ、0の横に100個、1の横にa個、3の横にb個置くとする。
    • この場合パス数は101*(a+1)*bとなる。あとは101*(a+1)*b=sとなるような、200よりは小さいa,bを見つければよい。
  a
  |
0-1-2-3
100 b

他はこんな方法があるようだった。

  • ∋-∈型を作り、足りない分は1箇所だけ点を連結して微調整。
  • 0-1-2-3の横にそれぞれa,b,c,d個点をつけ、(1+a*b+b*c+c*d)=sとなるようなa,b,c,dを総当たりで求める。
class TreeAndPathLength3 {
	public:
	vector <int> construct(int s) {
		vector<int> V;
		int i;
		if(s<=497) {
			FOR(i,s+2) V.push_back(i),V.push_back(i+1);
		}
		else {
			for(int a=1;a<=300;a++) {
				int tot=101*(a+1);
				if(tot>s) continue;
				int b=s-tot;
				if(b<=0 || b>=150) continue;
				
				V.push_back(0);
				V.push_back(1);
				V.push_back(1);
				V.push_back(2);
				V.push_back(2);
				V.push_back(3);
				FOR(i,100) V.push_back(0),V.push_back(4+i);
				FOR(i,a) V.push_back(1),V.push_back(104+i);
				FOR(i,b) V.push_back(3),V.push_back(104+a+i);
				break;
			}
		}
		return V;
	}
}

まとめ

自分のもちょっと回りくどい方法だけど、まぁ正解できたからいいかな…。
この問題はみんなアプローチがバラバラすぎてChallengeが難しかった。