色んな解き方がありそうな問題。
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
他はこんな方法があるようだった。
- ∋-∈型を作り、足りない分は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が難しかった。