みんなのプロコン2018 予選 : E - グラフの問題

実装は少し面倒だけど、やることが明らかなのでこちらの方が気楽。
https://beta.atcoder.jp/contests/yahoo-procon2018-qual/tasks/yahoo_procon2018_qual_e

問題

N頂点のグラフに対し、各頂点の次数の配列D[i]が与えられる。
そのような次数を満たす単純無向グラフは構築可能か。

構築できない場合、配列の要素を１つだけ1加算して構築可能か。

解法

次数の総和は偶数でなければならないので、奇数なら1加算することが確定する。
加算する場合は一番小さい要素に加算しておこう。

さて、その上でDが昇順であるよう並べ替え、小さい順に辺を張る相手を決めていく。
これは割と自明で、今見る頂点をiとすると辺の次数が多いD[i]個の頂点を選べばよい。
Dの上位D[i]個が次数が正だったら、そこと辺を結ぶことができる。
逆に次数が正の頂点がD[i]個なければ解なしである。

その際、Dの上位D[i]個をデクリメントするが、昇順が崩れかねない。
よって昇順であることを維持しつつ配列をデクリメントするデータ構造が必要である。
これはBITを使い直前の要素との差分を管理すればよい。

デクリメントする領域が、同じ値が連続する部分をぶった切る形になる場合、昇順が崩れるのでデクリメントする要素と同じ値を持つ部分は、少しデクリメントする位置をずらす。
これはlower_boundを備えたBITを持っておけば容易にできる。

int N;
int D[101010];
ll S;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<int,20> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>D[i+1];
		S+=D[i+1];
	}
	if(S%2) D[1]++;
	sort(D+1,D+N+1);
	for(i=1;i<=N;i++) {
		bt.add(i,D[i]-D[i-1]);
	}
	bt.add(N+1,1<<30);
	
	for(i=1;i<=N;i++) {
		x=bt(i);
		if(x==0) continue;
		bt.add(i,-x);
		bt.add(i+1,x);
		if(x>N-i || bt(N+1-x)==0) return _P("ABSOLUTELY NO\n");
		
		if(bt(N+1-x)!=bt(N-x)) {
			bt.add(N+1-x,-1);
			continue;
		}
		y=bt(N+1-x);
		j=bt.lower_bound(y);
		k=bt.lower_bound(y+1);
		int did=N+1-k;
		bt.add(j,-1);
		bt.add(j+(x-did),1);
		bt.add(k,-1);
	}
	
	
	if(S%2) _P("NO\n");
	else _P("YES\n");
}

まとめ

この昇順を維持しつつデクリメントするデータ構造、前にも使ったのに忘れてた…。