普通のSRMなら450ptかも。
http://community.topcoder.com/stat?c=problem_statement&pm=14933
問題
N頂点のシンプルグラフのうち、全頂点の次数が2となるものを作成したい。
今すでにいくつかの辺が与えられている。
辺を追加して条件を満たすものを作成する際、追加する頂点対を並べたとき辞書順最小のものを求めよ。
解法
今ある状態を見て、そのまま処理を続けていくと条件を満たせるかどうかはO(N)で判定できる。
よって辞書順最小の範囲で辺の候補を1個足しては継続可能かチェックしてみればよい。
継続可能な条件は下記のとおりである。
- 次数が1の頂点が4個以上のとき、必ず継続できる。
- 次数が1の頂点が2個のとき、以下のいずれかを満たせば継続できる。
- その2点間にまだ辺がない
- 他に次数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; } }
まとめ
発想は単純なんだけど、もれなく1発で通すの結構大変そう。