SRM 704 Div1 easy : TreeDistanceConstruction

問題概要：
次の制約を満たすような木は存在するか？

1. 木の頂点iのeccentricityがちょうどd[i]である.

ここで、頂点iのeccentricityとは、頂点iから最も遠い頂点との距離のことである.
存在するのであればその木の辺集合を配列にして返すこと.
存在しないのであれば空の配列を返すこと.

制約：
頂点数は高々50

解法：
答えとなる木の中で、最も離れている頂点対(i,j)について考える.
この２点をつなぐ長さd[i]のパスが存在するはずなので、そのパスを用意する.
そのパス上の最も離れた頂点対以外の頂点になりうる入力中の頂点が存在するはずなので、
それらを見つけてパスの頂点と対応付ける.
あとは入力中のまだどこにも対応付けられていない頂点を、そのパス上の適切な頂点に繋げればよい.
適切な頂点というのは、頂点iのeccentricityがd[i]であるときeccentricityがd[i]-1であるような頂点のことである.
マイナス1してあるのは、その頂点に辺を張ることでeccentricityが1増えるため.
残った頂点のeccentricityは最もd[i]以下かつ(パスの長さ)/2より大きいはずである.

例えば、Examplesの0)について考えてみる.
Examples 0) の入力は {3,2,2,3}なので、最も離れている頂点対は(0,3)である(0-indexed).
それでは、まず最初にこの２点をつなぐパスを作る.
このパスは以下の図のようになる.

最も離れている頂点対以外のパス上の頂点のeccentricityは？となっているが、
これらのeccentricityは明らかに2である.

この例だとこれで条件を満たす木ができたので終わり.

Examples 1)についても考えて見る.
入力は {1,2,2,2}である.
まず最初に最も離れている頂点対からパスを作る.

次にパスの中のでまだ入力中の頂点と対応付けられていない頂点に対して入力中の頂点を対応付ける.

あとは、残った入力中の頂点1をパス上の適切な頂点に繋げればよい.
頂点1のeccentricityは2なので、パス上のeccentricityが1の頂点に繋げばよい.

最後に、Examplesにはないが少し大きめの例について考えて見る.
入力は{4,4,3,2,3,4,4,3}とする.
まず最初に最も離れている頂点対からパスを作る.

次に、パス上の頂点と入力上の頂点を対応付ける

最後に、入力中の残った頂点をパス上の適切な頂点に繋げる.
まず、頂点5はeccentricityが4であるため、eccentricityが3であるような頂点に繋げば良い.

頂点6もeccentricityが4であるため、eccentricityが3であるような頂点に繋げば良い.

最後に、頂点7のeccentricityは3なので、eccentricityが2であるような頂点に繋ぐ.

完成である.

コード：

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS 1e-10
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

const int IINF = INT_MAX;

struct Data {
  int index;
  int eccentricity;
  bool operator < ( const Data &data ) const {
    return eccentricity > data.eccentricity;
  }
};

class TreeDistanceConstruction {
public:
  vector <int> construct(vector <int> d) {
    deque<Data> deq;
    int n = d.size();
    rep(i,n) deq.push_back((Data){i,d[i]});
    d.clear();
    sort(deq.begin(),deq.end());
    int maxi = deq[0].eccentricity;

    if( maxi != deq[1].eccentricity ) return vector<int>();
    vector<vector<int>> G;
    int root = (maxi+1) / 2;
    rep(i,(maxi+1)) {

      G.push_back(vector<int>());

      G[i].push_back(-1); // G[i][0], index

      if( (maxi+1) & 1 ) { // G[i][1], eccentricity
	if( i <= root ) G[i].push_back(maxi-i);
	else            G[i].push_back(i);
      } else {
	if( i < root ) G[i].push_back(maxi-i);
	else            G[i].push_back(i);
      }
      
      if( i + 1 < (maxi+1) ) G[i].push_back(i+1);
      if( i - 1 >= 0 ) G[i].push_back(i-1);

    }
    
    G[0][0] = deq.front().index; deq.pop_front();
    G[(int)G.size()-1][0] = deq.front().index; deq.pop_front();

    REP(i,1,(int)G.size()-1) {
      int pos = -1;
      rep(j,(int)deq.size()) {
	if( deq[j].eccentricity == G[i][1] ) {
	  pos = j;
	  break;
	}
      }
      if( pos == -1 ) return vector<int>();
      G[i][0] = deq[pos].index;
      deq.erase(deq.begin()+pos);
    }
    
    rep(i,(int)deq.size()) {
      if( deq[i].eccentricity <= root ) return vector<int>();
      G.push_back(vector<int>());
      G[(int)G.size()-1].push_back(deq[i].index);
      G[(int)G.size()-1].push_back(deq[i].eccentricity);
      G[(int)G.size()-1].push_back(deq[i].eccentricity-1);
      G[deq[i].eccentricity-1].push_back((int)G.size()-1);
    }

    vector<int> answer;
    rep(i,(int)G.size()) {
      REP(j,2,(int)G[i].size()) {
	int s = G[i][0];
	int t = G[G[i][j]][0];
	if( s < t ) {
	  answer.push_back(s);
	  answer.push_back(t);
	}
      }
    }
    return answer;
  }
};