あけましておめでとうございます。
https://yukicoder.me/problems/no/630
問題
正整数N,Mが与えられる。
以下を満たす無向グラフを構築せよ。
- N頂点M辺からなる連結グラフである。
- 各頂点には1~10^5のいずれかの値を設定できる。
- 長さ2のパスを選んだ時、そのパス上の3頂点の設定値が門松列を成す。
解法
奇数長の閉路ができてしまうと、そこは門松列が満たせない。
よって、奇数長の閉路を作らないようにしよう。
Mが大きい場合、辺をできるだけ多く張るためにはN頂点を均等に分けて二部グラフにするとよい。
よってN頂点を半分ずつにわけ、半分は小さい異なる値、半分は大きい異なる値を振ろう。
まず(N-1)個辺を張ってグラフを連結にし、それでももっと辺が必要なら、2部グラフの両端に詰め込めるだけ辺を追加していけばよい。
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の記事書き終えてない…。