TopCoder SRM 717 Div1 Easy ScoresSequence

EasyもMediumもまともに解けなかったけど4Challengeで被害は抑えた。
https://community.topcoder.com/stat?c=problem_statement&pm=14577

問題

N頂点の有向グラフを考える。
異なる2頂点(u,v)間はu→vかv→uのいずれかの辺が張られている。
ここで、各頂点における出次数の配列Sが与えられる。

頂点対(a,b)のうち有向辺をたどりa→bに遷移できるものの組み合わせは何通りか。

解法

Sを昇順にソートしておこう。
仮に閉路がない場合、Sは0,1,2...,(N-1)となる。
この場合、配列中で後ろにあたる頂点は前にある頂点に辺が伸びており遷移可能で、その逆はないため、N*(N+1)/2通りの遷移があることが確定する。
Sと0,1,2....の差を取ったときに増減がある場合、一部配列中手前の頂点から奥の頂点への辺があることになる。
たとえばa→b(a＜b)に辺がある場合、a～bの間は互いに移動可能なので、その分(b-a)*(b-a-1)/2通りだけ答えに追加する。

この逆向きの辺の割り当てを考えよう。
配列を端から見て、(S[i]-i)が正または負の頂点は出次数が過剰または不足していることになる。
スタックを使い過剰な頂点と不足の頂点のマッチングを取り、その間に逆向きの辺があると考えればよい。

class ScoresSequence {
	public:
	int count(vector <int> s) {
		int N=s.size();
		sort(ALL(s));
		int i;
		int tot=N*(N+1)/2;
		vector<int> V;
		FOR(i,N) {
			s[i]-=i;
			if(s[i]>0) {
				while(s[i]&&V.size()&&V.back()<0) {
					if(V.size()==1) tot+=(i+V.back()+1)*(i+V.back()+2)/2;
					V.pop_back();
					s[i]--;
				}
				while(s[i]) V.push_back(i+1),s[i]--;
			}
			if(s[i]<0) {
				while(s[i]&&V.size()&&V.back()>0) {
					if(V.size()==1) tot+=(i-V.back()+1)*(i-V.back()+2)/2;
					V.pop_back();
					s[i]++;
				}
				while(s[i]) V.push_back(-(i+1)),s[i]++;
			}
		}
		
		return tot;
	}
}
||<	

*まとめ

他の回答者を見ると、ほかにもマッチングの取り方はあるみたいね。