Codeforces #306 Div2 D. Regular Bridge

シンプルな問題設定かつConstructiveというCFらしい問題。
http://codeforces.com/contest/550/problem/D

問題

整数Kが与えられる。
各頂点の次数がKで、橋を含む無向グラフを構築せよ。

解法

橋の両端の頂点をA-A'とし、A側はA,B,C....,、A'側はA',B',C',...からなるグラフを作ることを感がる。
A側とA'側は対称な形状を作ればいいので、以下片方A側だけを考える。

まずK=1の時はサンプル通りA-A'をそのまま答えればよい。
またKが偶数のときは条件を満たすグラフを構築できない。

A側のグラフを考えると、頂点AはA'を除きA側のグラフ内で次数(K-1)、他の頂点は次数Kでなければならない。
すなわち、次数が奇数の点が1個だけの状態にある。
グラフに辺を増減すると、次数が奇数の点は2個単位で増減する。
よってどう辺を追加しても次数が奇数の点を1個だけにすることはできない。

残りはKが3以上の奇数の場合である。
頂点AにB,Cを加える。また、D,E,F....と(K-1)個の頂点を考える。
この状態で以下のように辺を張ると良い。

• AとD,E,F....の間に辺を張る。
• BとD,E,F....の間に辺を張る。
• CとD,E,F....の間に辺を張る。
• BとCの間に辺を張る。

この状態で、A,B,Cは次数Kである。
D,E,F...はまだ次数3なので、あと(K-3)次数を追加しなければならない。
そこで、D,E,F...を円形に並べたとき、円周上で隣に来る点以外の各点と辺を結ぶとよい。
D,E,F...は(K-1)個の頂点からなるので、自分と両隣の点と辺を結ばなければ残り(K-3)個の頂点と辺を結べる。

A',B',C'...も同様に考えられる。

int K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K;
	
	if(K%2==0) {
		_P("NO\n");
	}
	else if(K==1) {
		_P("YES\n2 1\n1 2\n");
	}
	else {
		vector<pair<int,int> > P;
		
		P.push_back(make_pair(1,4));
		P.push_back(make_pair(2,3));
		P.push_back(make_pair(5,6));
		FOR(i,K-1) {
			P.emplace_back(1,7+i);
			P.emplace_back(2,7+i);
			P.emplace_back(3,7+i);
			P.emplace_back(4,7+i+K-1);
			P.emplace_back(5,7+i+K-1);
			P.emplace_back(6,7+i+K-1);
		}
		FOR(x,K-1) for(y=x+1;y<K-1;y++) {
			if((x^1)==y) continue;
			P.emplace_back(7+x,7+y),P.emplace_back(7+x+K-1,7+y+K-1);
		}
		
		_P("YES\n");
		_P("%d %d\n",6+2*(K-1),P.size());
		FORR(r,P) _P("%d %d\n",r.first,r.second);
	}
}

まとめ

なかなか面白かったです。