不安だったけど通ってよかった。
http://codeforces.com/contest/755/problem/E
問題
N頂点の無向グラフを考える。
各2頂点対の間は、赤白どちらかで塗られた辺をもつものとする。
ここで整数Kが与えられる。以下の条件を満たすグラフを構築せよ。
- 赤い辺および白い辺それぞれで各頂点が連結している。
- 赤い辺および白い辺それぞれにおける最遠点対を考えたとき、両者の距離の小さい方はKである。
解法
- N≦3だとそもそも連結の条件を満たせない。
- N=4のとき、1-2-3-4と4頂点を片方の色で一列に並べないと連結の条件を満たせず、その時K=3である。
- N≧5のとき、K≧4にすることはできない。どうしてもどちらかの色の最遠点対の距離は3以下になる。
- K=2の場合、1-2-...-Nと全頂点を片方の色で1列に並べる。残りの頂点対をもう片方の色にすると、そちらの最遠点対の距離は2となる。
- K=3の場合、N=4の例になぞらえ1-2-3-4と4頂点を片方の色で並べ、また2番の頂点に残りの点を同じ色の辺ですべてつなごう。このグラフは明らかに直径3である。
- 残りの頂点対をもう片方の色でつなぐと、2と3の距離は3になる。
int N,K; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; if(K==2 && N>4) { cout<<N-1<<endl; FOR(i,N-1) { cout<<(i+1)<<" "<<(i+2)<<endl; } } else if(K==3 && N>=4) { cout<<N-1<<endl; cout<<"1 2"<<endl; cout<<"2 3"<<endl; cout<<"3 4"<<endl; for(i=5;i<=N;i++) cout<<"2 "<<i<<endl; } else { cout<<-1<<endl; } }
まとめ
コードは短いけどちょっと考える問題。