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

Source

「みんなのプロコン 2018」予選
問題文

問題概要

整数列 $D_1, D_2, \ldots, D_N$ が与えられる.
$N$ 頂点の単純無向グラフであって,各頂点の次数が $D_1,D_2,\ldots,D_N$ であるものが存在するかどうかを判定する問題.
また,存在しないなら,どれか $1$ つの $D_i$ を $1$ だけ増加したときに,それを次数とするような単純無向グラフが存在するかどうかを判定する.

解法

次数が与えられたときに,対応する単純グラフが存在するかどうかは,Havel-Hakimi algorithmErdos-Gallai theorem が知られている.
高速な実装が要求される場合は後者のほうが使いやすい.
例えば検索すれば,Erdos-Gallai test in linear time が出てきて,時間計算量 $O(N)$ の模擬コードが載っている.

さて,それを前提に問題を考える.
まず,大前提として,次数の合計は偶数である.
ので,$\sum D_i$ が偶数ならば,どこかの $D_i$ を $1$ つ増やしたら,そのようなグラフは存在しないので,普通に対応する単純グラフが存在するかどうかを判定すれば良い.
$\sum D_i$ が奇数ならば,最も次数の小さいノードに対して次数を $1$ 増やして判定すれば良い.
そうするのが最善である(それでグラフが存在しないなら他の $D_i$ を $1$ 増やしても単純グラフは存在しない)のはHavel-Hakimiのアルゴリズムを考えるとわかりやすい.

結局合計で時間計算量 $O(N)$ で解ける.

cLayversion 20180208-1)のコード

C++に変換後のコードはこちら

int N, D[100000];
ll H[100000];
{
  int i, j, k, fg = 0, w, y;
  ll sum;
  rd(N,D(N));

  sum = 0;
  rep(i,N) sum += D[i];
  if(sum%2==1){
    fg = 1;
    rep(i,1,N) if(D[i-1] < D[i]) break;
    D[i-1]++;
  }

  reverse(D, D+N);

  H[0] = D[0];
  rep(i,1,N) H[i] = H[i-1] + D[i];
  
  w = N-1;
  rep(i,N){
    while(w >= 0 && D[w] < i+1) w--;
    y = max(i,w);
    if(H[i] > (ll)(i+1)*y + H[N-1]-H[y]){
      wt("ABSOLUTELY NO");
      return 0;
    }
  }

  if(fg==0) wt("YES"); else wt("NO");
}

Current time: 2021年09月25日00時04分34秒
Last modified: 2018年02月12日18時45分22秒 (by laycrs)
Tags: Competitive_Programming AtCoder yahoo-procon2018-qual
トップページに戻る

Logged in as: unknown user (not login)

ログイン: