Codeforces ECR #055 : D. Maximum Diameter Graph

なぜSRMとかぶせるのか。
https://codeforces.com/contest/1082/problem/D

問題

N要素の整数列A[i]が与えられる。
以下の条件を満たす連結無向グラフを構築せよ。

• 多重辺や自己辺をもたない。
• 頂点iの次数はA[i]以下である。
• 上記条件を満たすもののうち、直径が最大である。

解法

まずN要素を連結するため、A[i]の総和が2*(N-1)以上であることを確認しよう。
その後、A[i]が2以上の要素を順につなげていく。
最後にA[i]が1の要素をまず上記列の先頭と末尾につなげ、それでも余れば他「A[i]が2以上の要素を順につなげていく」の余った場所に追加していく。

int N;
int A[505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int S=0;
	vector<int> B,C;
	FOR(i,N) {
		cin>>A[i];
		S+=A[i];
		if(A[i]>1) B.push_back(i);
		else C.push_back(i);
	}
	
	if(S<2*(N-1)) return _P("NO\n");
	
	int ret=(B.size()-1)+min(2,(int)C.size());
	vector<pair<int,int>> R;
	FOR(i,B.size()-1) {
		R.push_back({B[i],B[i+1]});
		A[B[i]]--;
		A[B[i+1]]--;
	}
	if(C.size()) {
		R.push_back({B[0],C.back()});
		A[B[0]]--;
		C.pop_back();
	}
	if(C.size()) {
		R.push_back({B.back(),C.back()});
		A[B.back()]--;
		C.pop_back();
	}
	
	FORR(b,B) {
		while(A[b] && C.size()) {
			A[b]--;
			R.push_back({b,C.back()});
			C.pop_back();
		}
	}
	cout<<"YES "<<ret<<endl;
	cout<<R.size()<<endl;
	FORR(r,R) cout<<(r.first+1)<<" "<<(r.second+1)<<endl;
	
	
}

まとめ

まぁこれは構築ゲーとしてもそこまで難しくはないかな。