UVa-10720 : Graph Construction

問題概要

長さN(<10^4)の数列が与えられる。ノード数Nのsimpleなグラフの次数列となりうるかどうかを判定する問題。

解法

ググるとErdős-Gallai の定理というのが出てくる。これを実装した。愚直な実装だと計算量O(N^2)で厳しいけど、累積和とか二分探索を使うとO(N*logN)で判定できる。でもテストケースが弱いのかO(N^2)でも通るらしい。謎。

acceptされたコード

計算量O(N*log N)。

#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;

const int MAX_N = 10000;

int N;
int ds[MAX_N];
int accum[MAX_N+1];

bool init(){
	scanf("%d",&N);
	for(int i=0; i<N; i++){
		scanf("%d", ds+i);
	}
	return N>0;
}

//[from, to)
int sum(int from, int to){
	return accum[to] - accum[from];
}

bool solve(){
	sort(ds, ds+N, greater<int>());

	for(int i=0; i<N; i++){
		accum[i+1] = accum[i] + ds[i];
	}

	if(accum[N]&1){
		return false;
	}

	for(int k=0; k<N; k++){
		int left = sum(0, k+1);
		int right = k * (k+1);

		int pos = lower_bound(ds , ds + N, k+1, greater<int>()) - ds;
		if(pos < k + 1){
			right += sum(k+1, N);
		}
		else{
			right += sum(pos, N) + (k+1)*(pos - (k+1));
		}

		if(left > right){
			return false;
		}
	}

	return true;
}

int main(){
	while(init()){
		puts( solve() ? "Possible" : "Not possible");
	}

	return 0;
}