Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

天下一プログラマーコンテスト2013予選B E - 天下一最短路コンテスト (テスター担当) (この記事を編集する[管理者用])

Source

天下一プログラマーコンテスト2013予選B
問題文

問題概要

まず,以下の問題を考える.
2次元平面上にN個の点が与えられるので,最初に与えられた点から出発して,全ての点を通るようなできるだけ短い経路を出力せよ.
この問題に対する貪欲なアルゴリズムとして,
・アルゴリズム1
 まだ通ってない最も近い点を選び,その点に行く,を繰り返す
・アルゴリズム2
 まだ通ってない点が3点以上あるなら,2番目に近い点に行く,を繰り返す
 まだ通ってない点が3点未満になったら,最も近い点に行く,を繰り返す
ただし,同じ距離の点が複数ある場合は,与えられた順番に近いとみなす.
この時,アルゴリズム2の方が,短いかアルゴリズム1と同じ長さの経路を返すようなデータセットを1つ求める問題.
Nが大きいほど点数が高く,N=100で満点だが,Nは100を超えてはいけない.

解法

適当にやればなんとでもなる.以下は解答の一例.
アルゴリズム2が良い結果を返す小さい点のパターンを見つけ,うまく繋げる
95点程度をほぼ1箇所に固めて,残りの点をランダムに配置して,条件を満たすまで繰り返す.(以下のコードはこれ)
アルゴリズム1の経路長 - アルゴリズム2の経路長などをスコアとして山登り,焼き鈍すなどの局所探索を行う.
はしご型や,規則正しく点を配置して,アルゴリズム2が勝つパターンを見つける.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
void llSort(ll d[],int s){int i,j;ll k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;i=-1;j=s;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}llSort(d,i);llSort(d+j+1,s-j-1);}

int N, x[1000], y[1000];

double dist(int a, int b){
  double dx, dy;
  dx = x[a] - x[b];
  dy = y[a] - y[b];
  return sqrt(dx*dx + dy*dy);
}

ll dist2(int a, int b){
  ll dx, dy;
  dx = x[a] - x[b];
  dy = y[a] - y[b];
  return dx*dx + dy*dy;
}



double hasi(){
  int i,j,k;
  int done[1000] = {1}, now = 0;
  ll d[1000]; int ds;
  double res = 0;

  for(;;){
    ds = 0;
    rep(i,N) if(!done[i]){
      d[ds++] = dist2(now, i) * 1000 + i;
    }
    if(!ds) break;
    llSort(d, ds);

    i = d[0] % 1000;
    res += dist(now, i);
    now = i;
    done[now] = 1;
  }
  return res;
}

double chokudai(){
  int i,j,k;
  int done[1000] = {1}, now = 0;
  ll d[1000]; int ds;
  double res = 0;

  for(;;){
    ds = 0;
    rep(i,N) if(!done[i]){
      d[ds++] = dist2(now, i) * 1000 + i;
    }
    if(!ds) break;
    llSort(d, ds);

    if(ds >= 3) i = d[1] % 1000;
    else        i = d[0] % 1000;
    res += dist(now, i);
    now = i;
    done[now] = 1;
  }
  return res;
}


int main(){
  int i,j,k;
  double t1, t2, best = 1e100;

  srand(time(NULL));
/*
  scanf("%d",&N);
  rep(i,N){
    scanf("%d%d",x+i,y+i);
  }
  t1 = hasi();
  t2 = chokudai();
  printf("%f %f\n",t1,t2);
  return 0;
*/
  N = 101;
  rep(i,101) x[i] = 5000 + i/10, y[i] = 5000 + i%10;

  for(;;){
    rep(i,5) x[N-1-i] = rand()%10001, y[N-1-i] = rand()%10001;
    t1 = hasi();
    t2 = chokudai();
/*    if(best > t2 - t1) best = t2 - t1;
    printf("%f %f %f\n",t1,t2,best);*/
    if(t1 > t2){
      k = 0;
      rep(i,N) REP(j,i+1,N) if(x[i]==x[j] && y[i]==y[j]) k++;
      if(!k) break;
    }
  }

  printf("%d\n",N);
  rep(i,N) printf("%d %d\n",x[i],y[i]);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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