Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Japan 2011 決勝 (参加記録) (この記事を編集する[管理者用])

2011年10月08日13時から3時間,5問.
[ Link ]

A, B, C, D-small, E-smallの92点で1位.らしくない順位をとってしまった.
日本限定ってことで,GCJらしくないセットだった.だからこそ戦えた感じ.
本家GCJではセンスが要求されるが,GCJJでは実装力と注意深さ的なのが要求されてる気がした.
大雑把な方針はすぐ見えるが,細かいところは地味に難しく,注意深く実装しないとバグるタイプの問題.
後,smallが強いのも特徴で,large用の解法でsmall通ると,だいたいlargeも通る気がする.
以下時系列順.

まずは全部問題を読む.
Aはgreedyでいいとして…,
Bは指数の方の周期はオイラーのファイ関数なのでそれでごにょごにょするだけだろう.
CはどうせDP,それぞれの文字列に対してどこまでマッチしているか(あるいはマッチしてる区間か?)を覚えてごにょごにょするだけ.
Dは…わからんなぁ…,smallは全探索だけど.
Eは…わからんなぁ…,smallはマップ作ってBFSするだけだろうけど.
A, B, Cを解くのは前提で,DとEを解けるか勝負っぽい.(気がしてた)
とりあえず,Aをさっくり通す.
B問題は…,あれ,(X^X)^(X^X)みたいな感じになるから,基数はmod Cで,指数はmod phi(C)で考えないといけない….
…,計算量爆発しませんか….
ああ,すべての時間について,バクテリアの数 mod 1, mod 2, ..., mod 1000をすべて計算しておけば,DPっぽくいける.
計算量 (logとか除けば) 1000^2で,テストケース500個あるけど,大丈夫か?
テストケース作って試したけど,大丈夫そう.
WAる.
phi[i]にすべきところを1箇所iにしてた.提出.
もう1時間近くたってしまってて絶望…,してたけど,みんなの点数も低い.
C問題は…,これ辞書順最小難しくないか??
とりあえず,普通にDPを書いてみる.
愚直に書いたら,O(50^6)とかになってしまった….
いや,それより,辞書順最小がむずい.
string使って富豪プログラミング…,まぁ,試しにね….
ランダムケース食わせると,1ケースあたり1秒ぐらい…,大丈夫かな,これ….
念のためO(50^5)に落としてみたけど,もともとO(50^5)のstringが重くて効果なし.
最悪ケースっぽいのを食わしても,どっちみち1秒で終わる.あれ,たぶん大丈夫だな….
small食わせると,答えの長さが無限大になってるケース (答えを見つけれてない) がいくつかある.
4分以内に修正しなきゃ…,最初や最後が*じゃないケースにまともに対応してなかったーーー.
4分オーバー.
修正してもう1回small,WAる.
smallの実行結果見ると明らかにおかしい…,対応しきれてなかった.
今度はsmall AC, largeも提出.
残り1時間10分ちょい.DもEもlarge考えてる暇はなく,smallを両方通す作戦に移行.
(Dは前の行の状態や道がどのようにつながってるかのDPであることに気づいたけど,そんなんやってられるかー)
Dの全探索をやる.
バグる….
あせる….
あう.
small実行.最後の方の答え5ばっかだなー.WA.
…,見つかった最大値を初期化するの忘れてる….だから5ばっかりだったんだよ…,もうちょっと怪しめ….
small AC.
この時点でなんでかしらないけど1位.
3分後にhosさんに抜かれて,自分のほうが1回WAが多くて,実質30秒差.
Eのsmallをやる.
線に近づけるのに気づいてなかった.
えっと…,めんどいです.
座標を縦横3倍に拡大して,座標/3の値が切り替わる移動だけコスト1にすればいいか.
マップを作って,01-BFSを書く.
答えが合わない.
マップが間違ってる….
直す.
答えが一瞬合う.
コメント消してるうちに答えが合わなくなる.
あれ….
結局何が悪かったのかわからなかったけどもう1回デバグすることになった.
1発でsmall AC.
残り時間10分では流石に後は何も出来ず.small 2つなんて30分あれば行けると思ってたのに….
みんなもっと解いてくると思ったのだけど,やってみると地味なところが難しいセットで,意外と手間取ってしまったようです.

以下は,D-smallとE-smallのコード.
A問題, B問題, C問題は個別の記事を参照.

Cによるスパゲッティなソースコード (問題D-small)
#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)

void unionInit(int d[],int s){int i;rep(i,s)d[i]=i;}
int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;}
int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;}

int res;
int x, y, xy;
char mp[60][60];

int must[60][60], must_fst;
int dame[60][60];

int ind[1000];

void solve(int a,int b,int now){
  int i,j,k;
  int ni,nj;

/*  puts("--------------");
  printf("%d %d\n",a,b);
  rep(i,x){ rep(j,y) printf("%d",dame[i][j]); puts(""); } puts("");
  rep(i,x){ rep(j,y) printf("%d",must[i][j]); puts(""); } puts("");*/

  if(a==x){
    if(res >= now) return;
    
    unionInit(ind, xy);
    rep(i,x) rep(j,y){
      if(i+1 < x && !dame[i][j] && !dame[i+1][j]) unionConnect(ind, i*y+j, (i+1)*y+j);
      if(j+1 < y && !dame[i][j] && !dame[i][j+1]) unionConnect(ind, i*y+j, i*y+j+1);
    }
    rep(i,x) rep(j,y) if(must[i][j]){
      if(unionGet(ind,must_fst) != unionGet(ind,i*y+j)) return;
    }

    if(res < now) res = now;
    return;
  }

  if(b==y){
    solve(a+1,0,now);
    return;
  }

  solve(a,b+1,now);

  i=a; j=b;
  if(i+1 < x && j+1<y && !dame[i][j] && !dame[i+1][j] && !dame[i][j+1]){
    dame[i][j]++;
    dame[i][j+1]++;
    must[i+1][j]++;
    solve(a,b+1,now+1);
    dame[i][j]--;
    dame[i][j+1]--;
    must[i+1][j]--;
  }

  if(i-1 >= 0 && j+1<y && !dame[i][j] && !dame[i-1][j+1] && !dame[i][j+1]){
    dame[i][j]++;
    dame[i][j+1]++;
    must[i-1][j+1]++;
    solve(a,b+1,now+1);
    dame[i][j]--;
    dame[i][j+1]--;
    must[i-1][j+1]--;
  }

  if(i+1 < x && j-1>=0 && !dame[i][j] && !dame[i+1][j] && !dame[i][j-1]){
    dame[i][j]++;
    dame[i+1][j]++;
    must[i][j-1]++;
    solve(a,b+1,now+1);
    dame[i][j]--;
    dame[i+1][j]--;
    must[i][j-1]--;
  }

  if(i+1 < x && j+1<y && !dame[i][j] && !dame[i+1][j] && !dame[i+1][j+1]){
    dame[i][j]++;
    dame[i+1][j]++;
    must[i+1][j+1]++;
    solve(a,b+1,now+1);
    dame[i][j]--;
    dame[i+1][j]--;
    must[i+1][j+1]--;
  }
}

int main(){
  int i,j,k,l,m,n;
  int size, count=0;

  scanf("%d",&size);
  while(size--){
/*    fprintf(stderr,"size %d\n",size);*/

    res = 0;
    scanf("%d%d",&x,&y);
    rep(i,x) scanf("%s",mp[i]);

    xy = x*y;

    rep(i,x) rep(j,y) must[i][j] = dame[i][j] = 0;
    rep(i,x) rep(j,y){
      if(mp[i][j]=='D'){
        must[i][j] = 1;
        must_fst = i*y + j;
      }
      if(mp[i][j]=='X') dame[i][j] = 1;
    }

    solve(0,0,0);
    printf("Case #%d: %d\n",++count,res);
  }

  return 0;
}
Cによるスパゲッティなソースコード (問題E-small)
#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 N 12000000
#define MX 3000

void charReverse(char d[],int size){int a=0,b=size-1;char t;while(a<b)t=d[a],d[a]=d[b],d[b]=t,a++,b--;}

char mp[MX][MX];
char meirei[N]; int len=1, now;
char mode;

#define ST 10000000
int q[20000000], q_st, q_size;
int dist[MX][MX];

int solve(int sx, int sy, int ex, int ey){
  int i,j,k;
  int ni, nj, add;
  int dx[4]={0,1,0,-1};
  int dy[4]={1,0,-1,0};

  q_st = ST; q_size = 0;
  rep(i,MX) rep(j,MX) dist[i][j] = -1;

  q[q_st+q_size++] = sx*MX + sy;
  dist[sx][sy] = 0;
  while(q_size){
    k = q[q_st++]; q_size--;
    sx = k/MX; sy = k%MX;

    if(sx==ex && sy==ey) return dist[sx][sy];

    rep(k,4){
      ni = sx + dx[k];
      nj = sy + dy[k];
      if(ni < 0 || nj < 0 || ni >= MX || nj >= MX) continue;
      if(mp[ni][nj]) continue;
      
      add = 0; if(ni/3 != sx/3 || nj/3 != sy/3) add = 1;

      if(dist[ni][nj]==-1 || dist[ni][nj] > dist[sx][sy]+add){
        dist[ni][nj] = dist[sx][sy]+add;
        if(add==0){
          q_st--; q_size++;
          q[q_st] = ni*MX+nj;
        } else {
          q[q_st+q_size++] = ni*MX+nj;
        }
      }
    }
  }

  return -1;
}

int main(){
  int i,j,k,l,m,n,res;
  int size, count=0;

  rep(i,MX) rep(j,MX) mp[i][j] = 0;

  int sx, sy, sd;
  int dx[4]={0,1,0,-1};
  int dy[4]={1,0,-1,0};

  sx = sy = 4; sd = 0;
  mp[sx][sy] = 1;

  now = 0;
  meirei[0] = 'X';
  mode = 'A';


  while(len < N){
    if(now == len){
      if(len*2 >= N) break;
      if(mode=='A'){
        mode = 'B';
        if(meirei[0]=='X') meirei[0] = 'L';
        else if(meirei[0]=='L') meirei[0] = 'X';
        k = len;
        rep(i,k){
          meirei[len++] = meirei[i];
          if(meirei[len-1]=='L') meirei[len-1] = 'R';
          else if(meirei[len-1]=='R') meirei[len-1] = 'L';
        }
      } else {
        mode = 'A';
        k = len;
        rep(i,k) meirei[len++] = meirei[i];
        charReverse(meirei+k, k);
/*        rep(i,len) putchar(meirei[i]); puts("");*/
      }
    }

    if(meirei[now]=='R') sd = (sd+1)%4;
    if(meirei[now]=='L') sd = (sd+3)%4;
    rep(i,6){
      sx += dx[sd];
      sy += dy[sd];
      if(0<=sx && sx<MX && 0<=sy && sy<MX) mp[sx][sy]=1;
    }
    now++;
  }

/*  rep(i,50){
    rep(j,50) putchar('0'+mp[i][j]); puts("");
  }puts("");*/


  scanf("%d",&size);
  while(size--){
    fprintf(stderr,"size %d\n",size);

    scanf("%d%d%d%d",&i,&j,&k,&l);
    res = solve(i*3+1,j*3+1,k*3+1,l*3+1);
    printf("Case #%d: %d\n",++count,res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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