kmjp's blog

競技プログラミング参加記です

Good Bye 2018 : E. New Year and the Acquaintance Estimation

うーむ、方針あってると思ったんだけどな。
https://codeforces.com/contest/1091/problem/E

問題

(N+1)頂点の無向グラフを考える。
N頂点分の次数が与えられているとき、全体が単純グラフとなるには(N+1)番目の頂点のあり得る次数vを列挙せよ。

解法

次数の総和は偶数でないといけないので、vの偶奇は明らか。
あとは、vの最小値と最大値を求めれば、その間で偶奇が合うものはすべて条件を満たす。
よってvの最小値と最大値だけを求めよう。

微妙に問題文にヒントが合った通り、次数に対し条件を満たすグラフが存在するかどうかは下記の式で判定できる。
Erdős–Gallai theorem - Wikipedia

一見、この定理では条件を満たす・満たさないの2値しか返さなそうだが、初めて条件に反するd_iがvより大きいかそうでないかを判定することで、vが小さすぎてダメだったか大きすぎてダメだったかもわかる。
よって、最小値最大値それぞれを二分探索で求めよう。
「小さすぎてダメ」ということのない最小値と、「大きすぎてダメ」ということのない最大値を求めればよい。

int N;
int A[502020];
int B[502020];
int M[502020];
int ret;

int hoge(int v) {
	int i;
	
	ll S=v;
	B[N]=v;
	FOR(i,N) B[i]=A[i], S+=A[i];
	
	sort(B,B+(N+1));
	reverse(B,B+(N+1));
	
	ll sum=0,mi=0;
	ZERO(M);
	for(int k=N+1;k>=1;k--) {
		mi+=M[k];
		sum-=1LL*M[k]*k;
		
		if(S>1LL*k*(k-1)+sum+mi*k) {
			if(B[k-1]<=v) return -1;
			else return 1;
		}
		
		S-=B[k-1];
		if(B[k-1]>=k) {
			mi++;
		}
		else {
			M[B[k-1]]++;
			sum+=B[k-1];
		}
		
	}
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	int par=0;
	FOR(i,N) {
		scanf("%d",&A[i]);
		par ^= A[i]&1;
	}
	
	
	int L=N-((N%2)!=par);
	if(hoge(L)==1) return _P("-1\n");
	for(i=20;i>=1;i--) if(L>=(1<<i) && hoge(L-(1<<i))<=0) L-=1<<i;
	if(hoge(L)!=0) return _P("-1\n");
	int R=par;
	if(hoge(R)==-1) return _P("-1\n");
	for(i=20;i>=1;i--) if(R+(1<<i)<=N && hoge(R+(1<<i))>=0) R+=1<<i;
	if(hoge(R)!=0) return _P("-1\n");
	
	
	if(L<=R) {
		for(i=L;i<=R;i+=2) _P("%d ",i);
	}
	else {
		_P("-1\n");
	}
	
	
}

まとめ

自分はHavel–Hakimi algorithm風の方式を取っていたのだけど、これだとダメだったようだ。
同じ間違いした人も数人いるね。