AOJ 1307 Towns along a Highway

Problem C: Towns along a Highway
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1307

問題概要

街が20個くらいある。
すべての街同士のペアの距離情報が与えられる。
考えられる全ての街の配置を求めよ。
一次元です。

解法

探索
まず、一番長い距離が、一番端の街同士の距離であることは間違えない。
この間に他の街を配置していく。
そのとき、今残ってる距離で一番長いもの、は、
間違えなく、両端の街のどちらかとの距離である。
よって、どちらもためしてやって矛盾しないかやってみる。
そこで今まで配置した街とも矛盾しないか比べる。
つかった距離を記憶する
というふうに探索すると
2^18くらいのオーダーに落ちる。

ソース

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;

const int D = 401;
const int N = 20;

int remainD[D];
int n, l;
vector<int> NOW;
set<vector<int> > S;

void solve(int now){
  if(now == n-2){
    vector<int> TMP = NOW;
    sort(ALL(TMP));
    S.insert(TMP);
    return;
  }
  for(int i = l-1; i> 0; i--){
    if(remainD[i] == 0 || remainD[l-i] == 0)continue;
    
    //front
    bool out =false;
    FOR(it, NOW){
      int &tmp =  remainD[abs(*it - i)];
        tmp--;
        if(tmp < 0){
          out = true;
        }
    }
    if(!out){
      NOW.push_back(i);
      solve(now+1);
      NOW.pop_back();
    }
    FOR(it, NOW){
      int &tmp =  remainD[abs(*it - i)];
      tmp++;
    }
    
    //back
    out =false;
    FOR(it, NOW){
      int &tmp =  remainD[abs(*it - (l-i))];
      tmp--;
      if(tmp < 0){
        out = true;
      }
    }
    if(!out){
      NOW.push_back(l-i);
      solve(now+1);
      NOW.pop_back();
    }
    FOR(it, NOW){
      int &tmp =  remainD[abs(*it - (l - i))];
      tmp++;
    }
    break;
  }
}

int main(){
  while(cin >> n ){
    if(n == 0)break;
    rep(i, D)remainD[i] = 0;
    rep(i, n*(n-1)/2){
      int t;
      cin >> t;
      if( i == 0 )l = t; 
      else remainD[t]++;
    }
    NOW.clear();
    NOW.push_back(0);
    NOW.push_back(l);
    S.clear();
    solve(0);
    FOR(it, S){
      rep(i, it->size()-1){
        if(i != 0)cout << ' ' ;
        cout << (*it)[i+1] - (*it)[i];
      }
      cout << endl;
    }
    cout<< "-----" << endl;
  }
  return 0;
}