TopCoderOpen 2018 Round2A Medium MakingRegularGraph

普通のSRMなら450ptかも。
http://community.topcoder.com/stat?c=problem_statement&pm=14933

問題

N頂点のシンプルグラフのうち、全頂点の次数が２となるものを作成したい。
今すでにいくつかの辺が与えられている。
辺を追加して条件を満たすものを作成する際、追加する頂点対を並べたとき辞書順最小のものを求めよ。

解法

今ある状態を見て、そのまま処理を続けていくと条件を満たせるかどうかはO(N)で判定できる。
よって辞書順最小の範囲で辺の候補を１個足しては継続可能かチェックしてみればよい。
継続可能な条件は下記のとおりである。

• 次数が1の頂点が４個以上のとき、必ず継続できる。
• 次数が1の頂点が２個のとき、以下のいずれかを満たせば継続できる。
  • その２点間にまだ辺がない
  • 他に次数0の点がある
• 次数が1の頂点が0個のとき次数0の点が0個か3個以上なら継続できる。

int need[1010];
int NG[1010];

class MakingRegularGraph {
	public:
	int N;
	int ok() {
		int i;
		int cnt[3]={};
		vector<pair<int,int>> V;
		FOR(i,N) {
			cnt[need[i]]++;
			if(need[i]==1) V.push_back({i,NG[i]});
		}
		
		if(cnt[1]>=4) {
			return 1;
		}
		else if(cnt[1]==0) {
			if(cnt[2]==0 || cnt[2]>=3) return 1;
			return 0;
		}
		else {
			
			if(V[1].first==V[0].second && cnt[2]==0) return 0;
			return 1;
		}
		
	}
	vector <int> addEdges(int n, vector <int> x, vector <int> y) {
		int i,j;
		N=n;
		FOR(i,n) need[i]=2;
		FOR(i,x.size()) {
			need[x[i]]--;
			need[y[i]]--;
			NG[x[i]]=y[i];
			NG[y[i]]=x[i];
		}
		vector<int> R,NGR(1,-1);
		FOR(i,N) {
			for(j=i+1;j<N;j++) if(need[i]&&need[j]) {
				if(NG[i]==j) continue;
				need[i]--;
				need[j]--;
				int pi=NG[i],pj=NG[j];
				NG[i]=j;
				NG[j]=i;
				if(ok()) {
					R.push_back(i);
					R.push_back(j);
				}
				else {
					need[i]++;
					need[j]++;
					NG[i]=pi;
					NG[j]=pj;
				}
			}
			if(need[i]) return NGR;
			
		}
		return R;
	}
}

まとめ

発想は単純なんだけど、もれなく１発で通すの結構大変そう。