Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Open 2010 Marathon Round 1 - Planarity (この記事を編集する[管理者用])

2010年05月20日02時から,4週間.
(TCO非参加者,Round 1免除者用に,Marathon Match 61として同じ問題で同時に開催)

Source

Problem Statement
standings
standings (Matathon Match 61)

問題概要

グラフが与えられるので,枝はまっすぐな線分でつながれているものとして,平面上にノードを配置して,枝の交わる回数を少なくせよ,という問題.
ノード数は10以上100以下,枝の数はノード数の2倍以上5倍未満.

自分の解法

最初ランダムにノードを配置する. その後,制限時間が終わるまで,以下の操作をする.
ランダムに1個の点を選んで,ランダムな場所に移動させて,交わる枝の数が減るなら,それを採用する.
連続で,何回も採用されないと,ときどき採用してみる.

自分の提出コードは記事の最後に載せています.

最終Full Submit直前のExample Submitの結果.

Example scores:
0) 44.0
1) 39.0
2) 4198.0
3) 550.0
4) 635.0
5) 60.0
6) 3374.0
7) 565.0
8) 205.0
9) 3040.0
参加記録

以下,時系列順のログです.

1日目 (2010年05月20日) ぐらい

とりあえず問題を読んだ.
問題文本文が1行だけとか,Marathonっぽくなく,シンプルな問題.
方針が立たない.

SRM前に,とりあえず,1点をランダムに選んで,ランダムに置き直して,答えがよくなるなら採用,を繰り返すだけのプログラムを書く.
しかも,1点動かしただけでも,毎回,全ての枝対に対して交差判定しなおす駄目コード.
まぁ,今回は参加するのは確定なので,とりあえずサブミット.
0.00点 → 94.78点 (未提出 → 暫定3位, 提出1回目)
え,良くて50点ぐらいかと思ってたのに,皆まだやる気のコード出してないんだなぁ.

2日目 (2010年05月21日) ぐらい

SRM後,とりあえず,高速化だけする.
1点を動かしたあとって,スコアの計算,その点に繋がっていない枝同士の交差判定はしなくていいよね.
おお,大きいテストケースで結構点数良くなった.
ただ,小さいケースだと局所解に落ち込んでいるんだろうなぁという感じがする.
一定回数,解が更新されないなら,リスタートしてみよう.
サブミット.
88.89点 → 96.36点 (暫定8位 → 暫定2位, 提出2回目)

5日目 (2010年05月24日) ぐらい

交わってる枝が多いノードを動かしやすくしてみた.
重くなっただけで効果が分からない….とりあえず,消した.
最初に,初期解を,枝の繋がっているノードの方に向かって動かすことで,多少初期値が良くなるのでやってみる.
89.55点 → 88.66点 (暫定13位 → 暫定16位, 提出3回目)
あれぇ….
もとに戻そうか…?
取り敢えずパラメータ変えてサブミット.
88.27点 → 89.16点 (暫定17位 → 暫定14位, 提出4回目)
うーむ.

11日目 (2010年05月30日) ぐらい

リスタートするのをやめて,連続で更新されないと,ときどき,結果が悪くなっても強制的に採用するようにする.
小さいケースでは良いけど,大きいケースだと,それに足を引っ張られて余計悪くなる.
まぁ,試しに提出してみる.
83.34点 → 86.39点 (暫定39位 → 暫定29位, 提出5回目)
小さいのは流石に良い解出さないと皆に抜かれてたっぽいのかなぁ,なんか順位は上がった.

その後17日ぐらい何もせずに終了.
暫定順位,438人中79位 (78.26点) と,いつも目標にしてる上位20%をギリギリキープしてたらしい.
今度はちゃんと真面目に焼きなましを試してみよう….

提出したスパゲッティなソースコード (C++)
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>
#include<set>
#include<queue>
#include<map>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<climits>
#include<sys/time.h>
using namespace std;

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

#define ll long long
#define VI vector<int> 

#define N 700

ll time_limit = 9500*1000;
ll get_time(){ timeval t; gettimeofday(&t, 0); return t.tv_sec*1000000LL + t.tv_usec; }

ll start_time;
VI G_res; int G_score;
VI res; int score;

int int_sign(int x){
  if(x<0) return -1;
  if(x>0) return 1;
  return 0;
}

int is_cross(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
  int k1,k2,t;

  k1 = int_sign((x2-x1)*(Y1-y1)-(X1-x1)*(y2-y1));
  k2 = int_sign((x2-x1)*(Y2-y1)-(X2-x1)*(y2-y1));
  if(k1&&k1==k2) return 0;
  if(k1==k2){
    if(x1==x2) x1=y1, x2=y2, X1=Y1, X2=Y2;
    if(x1>x2) t=x1,x1=x2,x2=t;
    if(X1>X2) t=X1,X1=X2,X2=t;
    if(x1<=X1&&X1<=x2) return 1;
    if(x1<=X2&&X2<=x2) return 1;
    if(X1<=x1&&x1<=X2) return 1;
    if(X1<=x2&&x2<=X2) return 1;
    return 0;
  }

  k1 = int_sign((X2-X1)*(y1-Y1)-(x1-X1)*(Y2-Y1));
  k2 = int_sign((X2-X1)*(y2-Y1)-(x2-X1)*(Y2-Y1));
  if(k1==k2) return 0;
  return 1;
}



int used[N][N];
int x[110], y[110];
int node, edge[110][110], ea[550], eb[550], es;
int edch[550][550], next[550][550], tmp[550];

int recheck[120][300000], recheck_size[120];

void recheck_gen(void){
  int i,j,n;

  rep(n,node) recheck_size[n]=0;
  rep(n,node) rep(i,es) REP(j,i+1,es){
    if(ea[i]==ea[j] || ea[i]==eb[j] || eb[i]==ea[j] || eb[i]==eb[j]) continue;
    if(ea[i]==n || eb[i]==n || ea[j]==n || eb[j]==n); else continue;

    recheck[n][recheck_size[n]++] = i*es+j;
  }
}

int get_score(void){
  int i,j,k,r=0;

  rep(i,es) REP(j,i+1,es) edch[i][j]=0;
  
  rep(i,es) REP(j,i+1,es){
    if(ea[i]==ea[j] || ea[i]==eb[j] || eb[i]==ea[j] || eb[i]==eb[j]) continue;
    edch[i][j] = is_cross(x[ea[i]],y[ea[i]],x[eb[i]],y[eb[i]],x[ea[j]],y[ea[j]],x[eb[j]],y[eb[j]]);
    r += edch[i][j];
  }

  if(r < score){
/*    fprintf(stderr,"%d -> %d\n",score,r);*/
    score = r;
    res.clear();
    rep(i,node) res.push_back(x[i]), res.push_back(y[i]);
  }

  return r;
}

void res_gen(void){
  if(G_score > score) G_score=score, G_res = res;
}

int do_move(int n,int nx,int ny,int fg){
  int i, j, k, ns = score, ress = 0;
  int sx = x[n], sy = y[n];
  
  x[n]=nx; y[n]=ny;

  rep(k,recheck_size[n]){
    i=recheck[n][k]/es; j=recheck[n][k]%es;
    next[i][j] = is_cross(x[ea[i]],y[ea[i]],x[eb[i]],y[eb[i]],x[ea[j]],y[ea[j]],x[eb[j]],y[eb[j]]);
    ns += next[i][j] - edch[i][j];
  }

  if(fg || ns < score || (ns==score && rand()%5==0)){
    if(fg || ns<score) ress = 1;
/*    if(ress) fprintf(stderr,"%d -> %d",score,ns);*/
    rep(k,recheck_size[n]){
      i=recheck[n][k]/es; j=recheck[n][k]%es;
      edch[i][j]=next[i][j];
    }
    used[sx][sy]=0; used[nx][ny]=1;

    res_gen();
    score = ns;
    res[2*n]=x[n]; res[2*n+1]=y[n];
    return ress;
  }
  
  x[n]=sx; y[n]=sy;

  return 0;
}

double Parameter = 1.9;
double nextX[120], nextY[120], edgeN[120];

void move_all(void){
  int i,j,k;
  double x1,x2,y1,y2;

  rep(i,node) nextX[i]=nextY[i]=edgeN[i]=0;
  rep(i,es){
    nextX[ea[i]] += x[eb[i]];  nextY[ea[i]] += y[eb[i]];  edgeN[ea[i]] += 1.0;
    nextX[eb[i]] += x[ea[i]];  nextY[eb[i]] += y[ea[i]];  edgeN[eb[i]] += 1.0;
  }

  x1=y1=1e100; x2=y2=-1e100;
  rep(i,node){
    if(edgeN[i] > 0.5){
      nextX[i] /= edgeN[i];  nextY[i] /= edgeN[i];
      nextX[i] -= x[i];  nextY[i] -= x[i];
      nextX[i] = x[i] + Parameter * nextX[i];
      nextY[i] = y[i] + Parameter * nextY[i];
    } else {
      nextX[i] = x[i];
      nextY[i] = y[i];
    }

    if(x1>nextX[i]) x1=nextX[i]; if(x2<nextX[i]) x2=nextX[i];
    if(y1>nextY[i]) y1=nextY[i]; if(y2<nextY[i]) y2=nextY[i];
  }

  rep(i,N) rep(j,N) used[i][j]=0;
  
  rep(i,node){
    x[i] = (int)((nextX[i] - x1)/(x2-x1) * (N-50) + 25);
    y[i] = (int)((nextY[i] - y1)/(y2-y1) * (N-50) + 25);
    while(used[x[i]][y[i]]){
      x[i] = rand()%N;
      y[i] = rand()%N;
    }
    used[x[i]][y[i]]=1;
  }
}


class Planarity{
public:
VI untangle(int V, VI in){
  int i,j,k,a,b,loop,restart=0,dame;
  int n,nx,ny;
  int ind[120];
  int deg[120];
  ll tm;
  double pi=acos(0)*2;
  
  start_time = get_time();
  srand(time(NULL));

  node=V;
  es=0;
  rep(i,node) rep(j,node) edge[i][j]=0;
  for(i=0;i<in.size();i+=2){
    a=in[i]; b=in[i+1];
    if(a>b) k=a,a=b,b=k;
    edge[a][b]=edge[b][a]=1;
    ea[es]=a; eb[es++]=b;
  }

  rep(i,node) ind[i]=i;
  rep(i,node) deg[i]=0;
  rep(i,es) deg[ea[i]]++, deg[eb[i]]++;
  
  G_score = score = 1000000000;
  rep(i,node){
    x[i] = (int)(350 + 320*cos(2*pi*ind[i]/node));
    y[i] = (int)(350 + 320*sin(2*pi*ind[i]/node));
  }
  rep(i,5) move_all();

  get_score();
  fprintf(stderr,"init  - %d\n",score);

  recheck_gen();
  dame=0; loop=0;

  for(;;){
    if( (loop++)%500==0 ){
      tm = get_time() - start_time;
/*      if(mul < tm*20/time_limit) mul = tm*20/time_limit;*/
      if(tm > time_limit) break;
    }

    n=rand()%node;
    do{
      nx=rand()%N; ny=rand()%N;
    } while( used[nx][ny] );

    k = do_move(n, nx, ny, (dame>node*30));
    if(!k) dame++; else dame=0;
/*    if(k) fprintf(stderr," (loop %d, node %d, deg %d)\n",loop,n,deg[n]);*/
  }

  res_gen();
  fprintf(stderr,"score - %d\n",G_score);
  fprintf(stderr,"loop  - %d\n",loop);
  fprintf(stderr,"rest  - %d\n",restart);
  return G_res;
}
};








int main(){
  int i, k, n, V;
  VI in,res;
  ll chk; double tim;
  Planarity hoge;

  scanf("%d",&V);
  scanf("%d",&n);
  rep(i,n){ scanf("%d",&k); in.push_back(k); }

  chk = get_time();
  res = hoge.untangle(V, in);
  tim = (get_time()-chk)/1000000.0;
  fprintf(stderr,"time: %.3lf sec\n",tim); fflush(stderr);

  sleep(1);
  rep(i,res.size()) printf("%d\n",res[i]);
  fflush(stdout);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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