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; }