yukicoder : No.630 門松グラフ

あけましておめでとうございます。
https://yukicoder.me/problems/no/630

問題

正整数N,Mが与えられる。
以下を満たす無向グラフを構築せよ。

• N頂点M辺からなる連結グラフである。
• 各頂点には1～10^5のいずれかの値を設定できる。
• 長さ２のパスを選んだ時、そのパス上の３頂点の設定値が門松列を成す。

解法

奇数長の閉路ができてしまうと、そこは門松列が満たせない。
よって、奇数長の閉路を作らないようにしよう。
Mが大きい場合、辺をできるだけ多く張るためにはN頂点を均等に分けて二部グラフにするとよい。

よってN頂点を半分ずつにわけ、半分は小さい異なる値、半分は大きい異なる値を振ろう。
まず(N-1)個辺を張ってグラフを連結にし、それでももっと辺が必要なら、２部グラフの両端に詰め込めるだけ辺を追加していけばよい。

int N,M;
int A[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) A[i]=i+1;
	
	vector<pair<int,int>> V;
	set<pair<int,int>> S;
	FOR(i,N/2) {
		V.push_back({i,i+N/2});
		S.insert({i,i+N/2});
		M--;
		if(i+N/2+1<N) {
			V.push_back({i,i+N/2+1});
			S.insert({i,i+N/2+1});
			M--;
		}
	}
	if(M<0) return _P("NO\n");
	
	FOR(i,N/2) {
		for(j=N/2;j<N && M;j++) {
			if(S.count({i,j})==0) {
				V.push_back({i,j});
				S.insert({i,j});
				M--;
			}
		}
	}
	
	if(M) return _P("NO\n");
	cout<<"YES"<<endl;
	FOR(i,N) {
		cout<<A[i];
		if(i<N-1) cout<<" ";
	}
	cout<<endl;
	FORR(v,V) {
		cout<<v.first+1<<" "<<v.second+1<<endl;
	}
}

まとめ

明けましておめでとうとかいいつつ、昨年のAdvent Calendar Contestの記事書き終えてない…。