Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年06月24日02時から,2週間.
(TCO Round 2非参加者用に,Marathon Match 62として同じ問題で同時に開催)

Source

Problem Statement
standings
standings (Matathon Match 62)
forum

問題概要

100*100以下の周期境界のライフゲームのルールと,初期状態,正整数N,Kが与えられる.
ルールは,自分の状態と,隣接8マスで生きてるマス目の数によって,自分が次のターンどうなるかが与えられる.
初期状態からN個以下のマス目を変更できるとして,Kターン後に生きてるマスをできるだけ多くする問題.
Nは最大で面積/16,Kは最大で20.

自分の解法

焼きなまし法.
1マス選んで反転させて,結果が良くなるならそれを採用する(もしくはそうじゃなくても時々採用)というのを繰り返す.
限界まで反転させていたら,既に反転させてたのを戻す.
限界まで反転させてなくても,既に反転させてたのを戻すのを行うこともある,これも,結果が良くなるなら採用という形.
反転させてたのを戻すとき,ときどき,隣の反転させてないセルを選んで,それを一緒に反転させて,よくなるかどうかの判定をすることもある.
後,1マス選んで,の選び方は,
 最後に反転させようとしてからの時間 + 前に反転させようとしたときに生きてるマスの増えた数 (つまり減った数のマイナス1倍)
 (実際に反転させたなら,またすぐに選ばれないように,いくらかマイナスする)
の値の大きい方から優先的に選ぶ.優先度の管理はヒープを用いた.
生きてるマスのシミュレーションは,最初は全部シミュレーションするけど,その後は,反転させたマスの影響下のみ再計算することで高速化する.

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

最終提出コードのExample Submitの結果.

Example scores: 
0) 0.6597222222222222
1) 0.0
2) 0.6698014629049112
3) 0.0
4) 0.7016540739228099
5) 0.8611111111111112
6) 0.3945578231292517
7) 0.5850340136054422
8) 0.3982800982800983
9) 0.6056910569105691
参加記録

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

1日目 (2010年06月24日) ぐらい

朝起きて,とりあえず問題を読んだ.
方針が立たないし,愚直にシミュレーションしたらそれだけで時間かかりそう….
1マス変更して,シミュレーションして,結果が良くなるなら採用,その状態からまた1マス選ぶ…とすると,間に合わなさそう?
ランダムに,初期状態に戻してNマス選んで変更,を繰り返す…,ってのが良さそうなのではないだろうか.
まぁ,まずは,シミュレーションするプログラムを書く.
愚直にかいたけど,意外と,時間かからないのかな…,サイズ次第たけど.
取り敢えず,参加するのは確定なので,適当に,ランダムにNマス選んで,01入れ替えて,最高スコアを返すだけのプログラムを提出してみる.
未提出 → 39.19点 (未提出 → 暫定25位, 提出1回目)
おそらく,何も変更せずに出している人を除けば,下から数えて1/3ぐらいの位置という,とてもまずい感じ.

夜.
意外と愚直に書いてもイテレーション回数が大きかったので,最初だけランダム,
その後,一番良かったところから,適当に1マス選んでよくなるなら採用,を繰り返す.
39.19点 → 44.53点 (暫定52位 → 暫定16位, 提出2回目)

2日目 (2010年06月25日) ぐらい

最初1/4だけ全ランダムに変更していた結果を利用してなくて,捨ててるというバグが発覚….
そして,捨てたほうがスコアが良いことが発覚.
最初から,1個選んで変更をすることにしよう…,てか焼き鈍しすればいいのでは.
取り敢えず,焼きなましは置いといて,中途半端に高速化.まだ高速化の余地はあるけど.
高速化は,1マス変えるだけなら,再計算するのは,変えた場所の周辺だけでいいよね,っての.
しかし,毎回前回計算した盤面をコピーするので,オーダー的には変わってないという(高速化の余地はあるってのはここのつもり)
それでも,高速化されて点数上がりそうなので,一応サブミットしてみる.
44.53点 → 47.60点 (暫定29位 → 暫定11位, 提出3回目)
高速化をちゃんとする.が,そんなに早くならなかった.コピーは軽いのかな.
ちょっと,適当に焼きなまししてみる…,効果あるのかわからん,Example Submitで確かめる.
全体的にスコア悪くなってる気がする…,うーむ.
焼きなましのパラメータの調整など,ちょっと悪くなる方向が採用されるのを少なくしてみた.
よくなってるのかよくわからないけど,取り敢えずサブミットしてみる.
47.60点 → 47.76点 (暫定16位 → 暫定12位, 提出4回目)
提出しても,よくなってるのかどうかわからないw

13日目 (2010年07月06日) ぐらい

いつの間にか暫定114位になってた.
現在の100位ボーダーは48.15点.高い….
逃げ切れるかもと思ってたけど甘かった.
Kターン後のマス目で,自分の周囲が死んでるセルが多いところを選ばれやすくしてみて,反転させるようにしてみる.
なんか,結果がおかしい….
変数名がかぶってたというケアレスミス.
修正してサブミット.
47.76点 → 47.72点 (暫定114位 → 暫定114位, 提出5回目)
変わらん….ちょっと重くなってるからなぁ….
完全ランダムに戻そう.そして,ちょっと高速化.
47.72点 → 47.80点 (暫定114位 → 暫定113位, 提出6回目)
スコア的には誤差.
自分の周囲が死んでるセルが選ばれやすいってのをもう1回書いてみる.
47.80点 → 47.56点 (暫定112位 → 暫定123位, 提出7回目)

14日目 (2010年07月07日) ぐらい

既に反転させたセルを戻すとき,その代わりに近くのセル反転させてみる近傍探索の近傍を加える.
なぜそんなことを考えたかというと,反転させたときに,よくなるから反転させたわけで,元に戻りにくいから,すぐ隣とか影響の及ぶセルと一緒に変えると変わりやすいかな,なんて.
47.56点 → 47.94点 (暫定129位 → 暫定110位, 提出8回目)
各セルの,反転して欲しい度を,最後に反転してからの時間+前に反転したときに生きてるマスの増えた数ぐらいで評価して,ヒープに突っ込んで,最初から取り出していくようにしてみる.
最初,時間の項のプラスマイナス逆にして駄目だと思ったらそうでもなかった.よくなってるかも分からないけど….
試しにサブミットしてみる.
47.94点 → 48.20点 (暫定110位 → 暫定105位, 提出9回目)
うぐぐ,100位が遠い.
学校のゼミの間中,ノートPCで実行させて,最適なパラメータを探す.
こういう,パラメータ弄るのをやるの初めてかも.
ゼミが終わった段階でこんなものかなって感じのをサブミット.
48.20点 → 48.63点 (暫定112位ぐらい → 暫定92位, 提出10回目)
わお.
家に帰って最適パラメータを探す続き.
取り敢えず,途中結果をサブミット.ちなみに,残り4時間.
48.63点 → 48.77点 (暫定96位ぐらい → 暫定86位, 提出11回目)
適当にパラメータ調整してたら,日付変わりそうな感じになったので,最終サブミット.
(終了2時間以上前に最終サブミットしないと,ミスったときに挽回できないので…)
48.77点 → 48.77点 (暫定92位ぐらい → 暫定92位ぐらい, 提出12回目)
あっれorz

最終的な暫定順位は95位 / 254人.
自分の点数が48.77,100位が48.71,ローカルで300ケースを実行させても0.5点とかそのぐらいは点数がばらつくので,100位に残れるかどうか,運次第だなぁ.

提出したスパゲッティなソースコード (読ませる気のない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 VS vector<string> 

#define RAND (rand()/(RAND_MAX+1.0))
#define EPS 1e-10

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

ll start_time;
VS G_res; int G_score, score;

int R, C, RC, N, K;
char rules[11];
char mp_init[120][120];

char **mp, do1[22][120][120], do2[22][120][120];
int dame_count, per;

int ap_lay[10][2];
double GETA1, GETA2;

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;
}

int hp1[10000], hp2[10000], hpi1[10000], hpi2[10000], hp1_size, hp2_size; double hd1[10000], hd2[10000];
double bases1, bases2;

void initialize(void){
  int i, j;

  R = G_res.size();
  C = G_res[0].size();
  RC = R*C;

  mp  = (char **)malloc(R * sizeof(char *));
  rep(i,R){
    mp[i]  = (char*) malloc(C*sizeof(char));
  }

  G_score = -1;
  dame_count = 0;

  hp1_size = hp2_size = 0;
  bases1 = bases2 = 0;
  rep(i,RC){
    hd1[i] = RAND / 1e8;
    doubleHeapInsert(i, hp1, hpi1, &hp1_size, hd1);
  }

  GETA1 = 10.0 / pow(RC,0.8);
  GETA2 =  5.0 / N;
}

void endialize(void){
  int i;

  rep(i,R) free(mp[i]);
  free(mp);
}


int simulation_first(void){
  int i,j,ii,jj,tm,cnt;

  rep(i,R) rep(j,C) do1[0][i][j]=mp[i][j];
  
  rep(tm, K){
    rep(i,R) rep(j,C){
      cnt = 0;
      REP(ii,-1,2) REP(jj,-1,2) if(ii||jj) cnt += do1[tm][(i+ii+R)%R][(j+jj+C)%C];
      do1[tm+1][i%R][j%C] = ap_lay[cnt][do1[tm][i%R][j%C]];
    }
  }

  cnt = 0;
  rep(i,R) rep(j,C) cnt += do1[K][i][j];
  if(cnt > G_score){
    G_score = cnt;
    rep(i,R) rep(j,C) G_res[i][j] = do1[0][i][j]+'0';
  }

  rep(tm, K+1) rep(i,R) rep(j,C) do2[tm][i][j] = do1[tm][i][j];

  return cnt;
}


void get_st_ed(int k, int tm, int *sx, int *ex, int *sy, int *ey){
  if(k==-1){ *sx=*sy=0; *ex=*ey=0; return; }
  *sx = k/C + 4*R - tm;
  *ex = k/C + 4*R + tm + 1;
  *sy = k%C + 4*C - tm;
  *ey = k%C + 4*C + tm + 1;
  if((*sx)+R < *ex) *ex = (*sx)+R;
  if((*sy)+C < *ey) *ey = (*sy)+C;
}

int simulation(int k1, int k2){
  int i,j,ii,jj,tm,cnt;
  int sx, ex, sy, ey, loop;

  if(k1>=0) do2[0][k1/C][k1%C] ^= 1;
  if(k2>=0) do2[0][k2/C][k2%C] ^= 1;
  
  rep(tm, K) rep(loop,2){
    if(loop==0) get_st_ed(k1, tm+1, &sx, &ex, &sy, &ey);
    if(loop==1) get_st_ed(k2, tm+1, &sx, &ex, &sy, &ey);
    
    REP(i,sx,ex) REP(j,sy,ey){
      cnt = 0;
      REP(ii,-1,2) REP(jj,-1,2) if(ii||jj) cnt += do2[tm][(i+ii)%R][(j+jj)%C];
      do2[tm+1][i%R][j%C] = ap_lay[cnt][do2[tm][i%R][j%C]];
    }
  }

  cnt = 0;
  rep(i,R) rep(j,C) cnt += do2[K][i][j];
  if(cnt > G_score){
    G_score = cnt;
    rep(i,R) rep(j,C) G_res[i][j] = do2[0][i][j]+'0';
  }

  return cnt;
}


int is_saiyou(int bef,int aft,double done){
  double go;
  double per = 10;
  if(bef < aft){ dame_count=0; return 1; }

  if(dame_count < per*3){ dame_count++; return 0; }

  go = 20*(1-done)*RAND;
  if(go > bef-aft && RAND < done && 15*RAND < dame_count/(double)per){ dame_count=0; return 1; }

  dame_count++; return 0;
}


void one_move(double done){
  int i, j, k, tm;
  int k1=-1, k2=-1;
  int sx,sy,ex,ey,loop;
  int aft, increase;
  double temp;

  if(hp2_size && (hp2_size==N || RAND < 0.22)){
    k2 = hp2[0];
    if(RAND < 0.3){
      k = rand()%4;
      if(k==0) k1 = (k2+1)%RC;
      if(k==1) k1 = (k2+C)%RC;
      if(k==2) k1 = (k2+RC-1)%RC;
      if(k==3) k1 = (k2+RC-C)%RC;
      if(mp_init[k1/C][k1%C]!=do1[0][k1/C][k1%C]) k1 = -1;
    }
  }
  if(k2<0){
    k1 = hp1[0];
  }

  aft = simulation(k1,k2);
  increase = aft - score;
  if(is_saiyou(score,aft,done)){
    score = aft;
    increase += 10;
    REP(tm, -1, K) rep(loop,2){
      if(loop==0) get_st_ed(k1, tm+1, &sx, &ex, &sy, &ey);
      if(loop==1) get_st_ed(k2, tm+1, &sx, &ex, &sy, &ey);
      REP(i,sx,ex) REP(j,sy,ey) do1[tm+1][i%R][j%C] = do2[tm+1][i%R][j%C];
    }
    if(k1>=0){
      hd1[k1] = -1e100;
      doubleHeapGoUp(hpi1[k1],hp1,hpi1,hd1);
      doubleHeapDelete(hp1,hpi1,&hp1_size,hd1);

      hd2[k1] = -increase + bases2 + RAND; bases2 += GETA2;
      doubleHeapInsert(k1,hp2,hpi2,&hp2_size,hd2);
    }
    if(k2>=0){
      hd2[k2] = -1e100;
      doubleHeapGoUp(hpi2[k2],hp2,hpi2,hd2);
      doubleHeapDelete(hp2,hpi2,&hp2_size,hd2);

      hd1[k2] = -increase + bases1 + RAND; bases1 += GETA1;
      doubleHeapInsert(k2,hp1,hpi1,&hp1_size,hd1);
    }
  } else {
    REP(tm, -1, K) rep(loop,2){
      if(loop==0) get_st_ed(k1, tm+1, &sx, &ex, &sy, &ey);
      if(loop==1) get_st_ed(k2, tm+1, &sx, &ex, &sy, &ey);
      REP(i,sx,ex) REP(j,sy,ey) do2[tm+1][i%R][j%C] = do1[tm+1][i%R][j%C];
    }
    if(k1>=0){
      hd1[k1] = -increase + bases1 + RAND; bases1 += GETA1;
      doubleHeapGoUp(hpi1[k1],hp1,hpi1,hd1);
      doubleHeapGoDown(hpi1[k1],hp1,hpi1,hp1_size,hd1);
    }
    if(k2>=0){
      hd2[k2] = -increase + bases2 + RAND; bases2 += GETA2;
      doubleHeapGoUp(hpi2[k2],hp2,hpi2,hd2);
      doubleHeapGoDown(hpi2[k2],hp2,hpi2,hp2_size,hd2);
    }
  }
}


class CellularAutomaton{
public:
VS configure(VS grid, string rules, int N__N, int K__K){
  int i, j, loop=0;
  ll elapsed_time;
  double done=0;

  start_time = get_time();
  srand(time(NULL));

  rep(i,9) rep(j,2){
    if(rules[i]=='-') ap_lay[i][j] = 0;
    if(rules[i]=='+') ap_lay[i][j] = 1;
    if(rules[i]=='=') ap_lay[i][j] = j;
    if(rules[i]=='X') ap_lay[i][j] = (j^1);
  }

  G_res = grid; N = N__N; K = K__K;
  initialize();

  rep(i,R) rep(j,C) mp_init[i][j] = mp[i][j] = grid[i][j]-'0';
  simulation_first();

  fprintf(stderr,"init score %d / %d : %lf\n",G_score,R*C,G_score/(double)(R*C));

  per = (int)(200.0/(K+2));
  
  for(;;){
    if(loop%per==0){
      elapsed_time = get_time() - start_time;
      if(elapsed_time > time_limit) break;
      done = elapsed_time / (double)time_limit;
    }

    one_move(done); loop++;
  }

  fprintf(stderr,"final score %d / %d : %lf\n",G_score,R*C,G_score/(double)RC);
  fprintf(stderr,"loop %d\n",loop);
  fprintf(stderr,"per %d\n",per);

  endialize();
  return G_res;
}
};

int main(){
  int i, R, N, K;
  VS in, res;
  ll chk; double tim;
  char buf[1000];
  CellularAutomaton hoge;

  scanf("%d",&R);
  rep(i,R){ scanf("%s",buf); in.push_back((string)buf); }
  scanf("%s",buf);
  scanf("%d%d",&N,&K);

  chk = get_time();
  res = hoge.configure(in, (string)buf, N, K);
  tim = (get_time()-chk)/1000000.0;
  fprintf(stderr,"time: %.3lf sec\n",tim); fflush(stderr);

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

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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