Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1955-8143ead6
この記事にトラックバックする(FC2ブログユーザー)

April 2011 Challenge 3問目 - Graphs in Euclidean Space (チャレンジ形式) (この記事を編集する[管理者用])

Source

codechef April 2011 Challenge 3問目 (チャレンジ形式)
Problem Statement
April 2011 Challengeの参加記録

問題概要

連結なノード数 N (300以下) のグラフのそれぞれの接点までの最小距離の行列が与えられる.
三角関係式を満たす. dist[a][b] は dist[a][k]+dist[k][b] 以下.
その距離の関係をできるだけ満たすように,各ノードをd次元のユークリッド空間に埋め込む問題.
dは1以上20以下で好きに選んで良い.
座標の値は絶対値が1000000を超えてはいけなくて,整数でなければいけない.
ノードaとbの間の,与えられたグラフ上での距離をdist[a][b]として,実際に埋め込んだユークリッド空間での距離をx[a][b]とすると,
 x[a][b] / dist[a][b]
の最大値をmax,最小値をminとして
 d * max / min
がスコアになる.スコアは小さいほど良い.

解法

最初ランダムに配置,
 x[a][b] / dist[a][b] = max
となるノード対を見付け出して,そのノード間の距離を縮める,
 x[a][b] / dist[a][b] = min
となるノード対を見付け出して,そのノード間の距離を広げる,を繰り返した.
どうやらうまい埋め込む多項式時間アルゴリズムがあるらしい….

C++言語のスパゲッティなコード
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<cmath>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)





void doubleHeapGoUp(int n,int hp[],int hpi[],double d[]){
  int k,m;
  if(!n) return;
  m=(n-1)/2;
  if(d[hp[m]]<=d[hp[n]]) return;
  k=hp[m]; hp[m]=hp[n]; hp[n]=k;
  hpi[hp[m]]=m; hpi[hp[n]]=n;
  doubleHeapGoUp(m,hp,hpi,d);
}

void doubleHeapGoDown(int n,int hp[],int hpi[],int hp_size,double d[]){
  int k,m;
  m=2*n+1; if(m>=hp_size) return;
  if(hp_size>m+1 && d[hp[m]]>d[hp[m+1]]) m++;
  if(d[hp[m]]>=d[hp[n]]) return;
  k=hp[m]; hp[m]=hp[n]; hp[n]=k;
  hpi[hp[m]]=m; hpi[hp[n]]=n;
  doubleHeapGoDown(m,hp,hpi,hp_size,d);
}

void doubleHeapInsert(int n,int hp[],int hpi[],int *hp_size,double d[]){
  hp[*hp_size]=n; hpi[n]=(*hp_size)++;
  doubleHeapGoUp((*hp_size)-1,hp,hpi,d);
}

int doubleHeapDelete(int hp[],int hpi[],int *hp_size,double d[]){
  int r=hp[0]; hpi[r]=-1;
  if( *hp_size==1 ){(*hp_size)--; return r;}
  hp[0]=hp[--(*hp_size)]; hpi[hp[0]]=0;
  doubleHeapGoDown(0,hp,hpi,*hp_size,d);
  return r;
}






#define RAND (rand()/(RAND_MAX+1.0))

#define N 999000
#define EPS 1e-10

int n;
int edge[310][310];

vector<int> final_res[310];

vector<double> res[310], tmp[310];
double res_score, tmp_score;

double sum_score;

void get_final_res(void){
  int i, k, d, mv;
  double mx, mi, tt;
  set< vector<int> > s;

  d = res[0].size();
  mx = mi = res[0][0];
  rep(i,n) rep(k,d){
    mx = max(mx, res[i][k]);
    mi = min(mi, res[i][k]);
  }

  rep(i,n){
    final_res[i].clear();
    rep(k,d){
      if(mx - mi > EPS) tt = (res[i][k] - mi) / (mx - mi);
      else              tt = 0.5;
      final_res[i].push_back( (int)( (tt-0.5) * 2 * N) );
    }

    if(s.count(final_res[i])){
      mv=0;
      for(;;){
        mv++;
        rep(k,d){
          final_res[i][k]+=mv;
          if(s.count(final_res[i])==0) break;
          final_res[i][k]-=mv;
        }
        if(k!=d)break;
      }
    }

    s.insert(final_res[i]);
  }
}


double get_dist_tmp(int i,int j,int d){
  int k; double res = 0;
  rep(k,d) res += (tmp[i][k]-tmp[j][k]) * (tmp[i][k]-tmp[j][k]);
  return sqrt(res);
}


int hp1[100000], hp1_inv[100000], hp1_size; double hp1_data[100000];
int hp2[100000], hp2_inv[100000], hp2_size; double hp2_data[100000];

void solver(void){
  int i,j,k,d,loop,ij;
  int a,b;
  double mx, mi, mid, dis;
  double lim1, lim2;
  double now_dist, tar_dist;
  double sa[21];
  double choose[310];

  d=tmp[0].size();

  rep(i,n) REP(j,i+1,n) hp1_inv[i]=hp2_inv[i]=-1;
  hp1_size = hp2_size = 0;
  rep(i,n) REP(j,i+1,n){
    ij = i*n + j;
    dis = get_dist_tmp(i,j,d);
    hp1_data[ij] =  dis/edge[i][j];
    hp2_data[ij] = -dis/edge[i][j];
    doubleHeapInsert(ij,hp1,hp1_inv,&hp1_size,hp1_data);
    doubleHeapInsert(ij,hp2,hp2_inv,&hp2_size,hp2_data);
  }

  rep(i,n) choose[i] = 1;

  lim1 = 0.3; lim2 = 2;
  for(loop=0;;loop++){
    mi = hp1_data[ hp1[0] ];
    mx = hp1_data[ hp2[0] ];
    tmp_score = d * mx / mi;

    if(tmp_score < res_score){
      res_score = tmp_score;
      rep(i,n) res[i] = tmp[i];
    }
/*    printf("%lf\n",tmp_score);*/

    if(loop==710) break;

    mid = (mx+mi)/2;
    
    if(loop%12==1) a = hp1[0]/n, b = hp1[0]%n;
    else           a = hp2[0]/n, b = hp2[0]%n;

    now_dist = hp1_data[a*n+b]*edge[a][b];
    rep(k,d) sa[k] = (tmp[b][k] - tmp[a][k]) / now_dist;
    tar_dist = mid*edge[a][b] - now_dist;
    if(tar_dist >   lim1) tar_dist =   lim1;
    if(tar_dist < - lim2) tar_dist = - lim2;

/*    printf("choose %d %d\n",a,b);
    printf("now,tar %lf -> %lf\n",now_dist,tar_dist);*/

    rep(k,d) tmp[a][k] -= sa[k] * tar_dist * choose[b] / (choose[a] + choose[b]);
    rep(k,d) tmp[b][k] += sa[k] * tar_dist * choose[a] / (choose[a] + choose[b]);
    choose[a]*=1.6; choose[b]*=1.6;
    
    rep(i,n) if(i!=a){
      dis = get_dist_tmp(i,a,d);
      if(i<a) ij = i*n + a;
      else    ij = a*n + i;
      hp1_data[ij] =  dis/edge[i][a];
      hp2_data[ij] = -dis/edge[i][a];
      doubleHeapGoUp(hp1_inv[ij],hp1,hp1_inv,hp1_data);
      doubleHeapGoDown(hp1_inv[ij],hp1,hp1_inv,hp1_size,hp1_data);
      doubleHeapGoUp(hp2_inv[ij],hp2,hp2_inv,hp2_data);
      doubleHeapGoDown(hp2_inv[ij],hp2,hp2_inv,hp2_size,hp2_data);
    }
    rep(i,n) if(i!=b){
      dis = get_dist_tmp(i,b,d);
      if(i<b) ij = i*n + b;
      else    ij = b*n + i;
      hp1_data[ij] =  dis/edge[i][b];
      hp2_data[ij] = -dis/edge[i][b];
      doubleHeapGoUp(hp1_inv[ij],hp1,hp1_inv,hp1_data);
      doubleHeapGoDown(hp1_inv[ij],hp1,hp1_inv,hp1_size,hp1_data);
      doubleHeapGoUp(hp2_inv[ij],hp2,hp2_inv,hp2_data);
      doubleHeapGoDown(hp2_inv[ij],hp2,hp2_inv,hp2_size,hp2_data);
    }
  }
}


void set_random(int d){
  int i,k;

  rep(i,n){
    tmp[i].clear();
    rep(k,d) tmp[i].push_back( (double)RAND );
  }
}


int main(){
  int i,j,k,l,m,d;
  int size;

  srand(time(NULL));
  sum_score=0;

  scanf("%d",&size);
  while(size--){
    scanf("%d",&n);
    rep(i,n) rep(j,n) scanf("%d",edge[i]+j);

    res_score = 1e100;

    set_random(n/60 + 2);
    solver();

    sum_score += res_score;
    get_final_res();
    d = final_res[0].size();

    printf("%d\n",d);
    rep(i,n){// break;
      rep(k,d){
        if(k) putchar(' ');
        printf("%d",final_res[i][k]);
      }
      puts("");
    }
  }

//  printf("%lf\n",sum_score);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1955-8143ead6
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。