kmjp's blog

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

8VC Venture Cup 2017 - Elimination Round : E. PolandBall and White-Red graph

不安だったけど通ってよかった。
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;
	}
}

まとめ

コードは短いけどちょっと考える問題。