Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

東京大学プログラミングコンテスト2010 (UTCP2010) (この記事を編集する[管理者用])

2010年07月04日12時から5時間,12問.
[UTPC2010 HP] [standing] [M-judge (problems)]

去年も参加させていただいたのですが,そのときは全く解けなかったのでリベンジ戦.(去年の記事)
10問正解で,リベンジ成功したみたいです.
提出して通ったコード一覧は,全部最後に付けておきます.
以下は問題別.

A. 期末試験!

けいおん!
やるだけ.
最速サブミットを目指したけど,全然遅かった.
問題文開くのが遅かったよ,1分ぐらいかかった気がするよ,とか宣ってみる….
取り敢えず,Accept.

B. 宝くじチェッカー

やるだけ.
intでオーバーフローするかどうか判断するのが面倒だったのでlong longにしておいた.
変数名間違えて4分ぐらい嵌った気がする.
いきなりの絶望感.
取り敢えず,Accept.

C. コンパイル

ぷよぷよ.コンパイルってそういう事か.
シミュレーション書くだけ.DFSを多用する.
Bで遅れた分は,これの実装速度で多少は巻き返したみたいなのかな?
これも,縦横のサイズ間違えたり,バグって遅れた.
取り敢えず,これも,Accept.

D. 無矛盾な単位系

グラフ作って,ワーシャルフロイドするときに,矛盾を発見したらその場でNoを返すようにしてみた.
あっさりAccept.

E. トーマス・ライトの憂鬱

ロックマンのパスワード…だったらしい.
2行2列で,全ての行,列が全部1ならそれだけで複数あるので,決まるところから決めていって,全部決まらないならNoでいいんじゃない?
ソートして前と後ろから眺めてgreedyに処理していく.Accept.

F. UTF-8

単なるDP.
それなりにサクっと書けたのに,バグにはまる.
ケアレスミス×2で,WA3回.そののちAccept.

G. 天体観測

星空のメモリア.
グーグル先生に回転行列教えてーって頼んで,後は,回して回して回して,z座標が全部正かどうか調べた.
1発コンパイルでAccept.

H. 迷い猫、走った

迷い猫オーバーラン.
単純なDPじゃないか…,と思ったらO(1000^3)になる.
うーん,わからんぞ?
二分探索+Greedyっぽい…と思ったら上手くいかない.
二分探索+DPか…?
何を状態にして,何を求めるのか,よく分からない.
そんなに答えは変なのにならなさそうなので,O(n^3)のDPで,枝刈りすればいけるんじゃない?
まぁ,O(1000^3)のDPを書く.
枝刈り面倒になったので,嘘っぽい枝刈りを追加して,送信してみる.
1発Accept…,ぇ.

I. 盗まれた宝石

今までの移動パターンが,どの禁止パターンの何文字目まで一致しているか,という情報を付与してBFSというよくある問題.
ただし,ちょっと実装が面倒.
最初に,マッチング情報から,どの方向に移動すると,どういうマッチング状況になるかのグラフを作る.がりがり.
で,普通にBFSする.がりがり.
サンプル合わない….
おっと,文字と方向が一致してなかった….
1個だけサンプル合わない.
禁止パターンがない場合に死んでる!
これ,サンプル親切すぎるだろう…,これないと面白かったのに,自分は苦しんでた.
サブミット.Accept.

J. 多項式の解の個数

解法がまったく想像できない.
1個ずつ解見つけて割っていくのかな…?
解の候補が絞られたらいいのだけど….
剰余取らないバージョンなら,±最低次の係数の約数/最高次の係数の約数 とかに絞られる気がする.
そんなの成り立たないよな…,一応書いてみる….
成り立たない.
そもそも割れない?
わからない.
諦める.
Ustreamで聞いてた解説の雰囲気から,無理ゲーだということはよくわかった.
まぁ,流石のきたまさ君だし….

K. ワープホール

うーん?
座標圧縮してDP?
いや,上手くいかない…,ある場所からある場所へ移動するときの組み合わせの数をうまく計算できない.
うーん?
座標圧縮なんてしなくていいから,各場所に行くまでの経路の数を覚えておけば,適当に包除原理っぽいことで計算できる.
書こう.
微妙に合わない….
あ,これだと重複してカウントしてる,修正.
答え合う.
サブミット.WA.
うー.
あ,ワープホールの出口が,ワープホールの一口に飛ぶ場合怪しい.
テストケース作る.本質的に同じケースのはずが答え違う.
修正.
サブミット.Accept.

L. 3つのシルエット

とても面倒な3次元幾何だと思う.
でも,どうするのかわからない.
捨てる.
解説聞くと,三角形分割して凸にした後,3次元の凸包カット使うみたい.

A. 期末試験! (CODE)

本番に提出した,C言語によるスパゲッティなコードです.
Accepted, 0.01sec.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

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


int in[1000000];
int main(){
  int i,j,k,l,m,n;

  scanf("%d",&n);
  rep(i,n){
    k=0;
    rep(j,5) scanf("%d",&l), k+=l;
    in[i]=k;
  }

  intSort(in,n);
  printf("%d %d\n",in[n-1],in[0]);

  return 0;
}
B. 宝くじチェッカー (CODE)

本番に提出した,C言語によるスパゲッティなコードです.
Accepted, 0.01sec.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

char in[1000][100]; int val[1000];
char tmp[100];

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

  scanf("%d%d",&n,&m);
  rep(i,n) scanf("%s%d",in[i],val+i);

  rep(i,m){
    scanf("%s",tmp);
    rep(j,n){
      rep(k,8){
        if(in[j][k]=='*') continue;
        if(in[j][k]==tmp[k]) continue;
        break;
      }
      if(k==8) res += val[j];
    }
  }
  printf("%lld\n",res);

  return 0;
}
C. コンパイル (CODE)

本番に提出した,C言語によるスパゲッティなコードです.
Accepted, 0.01sec.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define X 12
#define Y 6

char in[100][100];
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};

int cnt;

void gogo(int i, int j, char from, char to, int fg){
  int k, ni, nj;

  if(in[i][j]==from){
    cnt++; in[i][j]=to;
    rep(k,4){
      ni = i+dx[k]; nj = j+dy[k];
      if(ni<0||nj<0||ni>=X||nj>=Y) continue;
      gogo(ni,nj,from,to,fg);
    }
  }
  if(in[i][j]=='O' && fg) in[i][j]='.';
}

int main(){
  int i,j,k,l,m,n,ok;
  int tm;

  rep(i,X) scanf("%s",in[i]);

  for(tm=0;;tm++){
    ok=0;
    rep(i,X) rep(j,Y) if('A'<=in[i][j] && in[i][j]<='Z') if(in[i][j]!='O') {
      cnt=0;
      gogo(i,j,in[i][j],in[i][j]-'A'+'a',0);
      if(cnt>=4){
        ok=1;
        gogo(i,j,in[i][j],'.',1);
      }
    }
    if(!ok) break;

    rep(j,Y){
      k=X-1;
      for(i=X-1;i>=0;i--) if(in[i][j]!='.') in[k--][j]=in[i][j];
      for(i=k;i>=0;i--) in[i][j]='.';
    }

    rep(i,X) rep(j,Y) if('a'<=in[i][j]&&in[i][j]<='z') gogo(i,j,in[i][j],in[i][j]-'a'+'A',0);

/*    rep(i,X) puts(in[i]); puts("");*/
  }

  printf("%d\n",tm);

  return 0;
}
D. 無矛盾な単位系 (CODE)

本番に提出した,C言語によるスパゲッティなコードです.
Accepted, 0.07sec.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define ull unsigned ll

#define ULL_HASH_SIZE 2000
ull ull_hash_n[ULL_HASH_SIZE]; int ull_hash_d[ULL_HASH_SIZE];

void ullHashClear(void){ memset(ull_hash_d,0,ULL_HASH_SIZE*sizeof(int)); }
int ullHashFunction(ull a){ return (a*1007)%ULL_HASH_SIZE; }

int ullHashGet(ull a){
  int i=ullHashFunction(a);
  for(;;){
    if(ull_hash_n[i]==a && ull_hash_d[i]) break;
    if(!ull_hash_d[i]) break;
    i++; if(i==ULL_HASH_SIZE) i=0;
  }
  if(ull_hash_n[i]!=a) return 0; return ull_hash_d[i];
}

void ullHashSet(ull a,int n){
  int i=ullHashFunction(a);
  for(;;){
    if(ull_hash_n[i]==a && ull_hash_d[i]) break;
    if(!ull_hash_d[i]) break;
    i++; if(i==ULL_HASH_SIZE) i=0;
  }
  ull_hash_n[i]=a; ull_hash_d[i]=n;
}

int ullHashIncrease(ull a){
  int i=ullHashFunction(a);
  for(;;){
    if(ull_hash_n[i]==a && ull_hash_d[i]) break;
    if(!ull_hash_d[i]) break;
    i++; if(i==ULL_HASH_SIZE) i=0;
  }
  ull_hash_n[i]=a; return ++ull_hash_d[i];
}

int number;
char tmp_string[1000];

int get_next(void){
  int i; ull hs=0;
  scanf("%s",tmp_string);
  for(i=0;;i++){
    if(tmp_string[i]<' ') break;
    hs = hs*1007+tmp_string[i];
  }
  i=ullHashGet(hs); if(i>0) return i-1;
  ullHashSet(hs,number+1); return number++;
}

void get_clear(void){
  number=0; ullHashClear();
}


#define INF 9817249

int main(){
  int i,j,k,l,m,n,dame;
  int in[200][200];
  char dum[100];

  scanf("%d",&n);
  rep(i,200) rep(j,200) in[i][j] = INF;
  rep(i,200) in[i][i]=0;

  get_clear();
  while(n--){
    scanf("%d",&k);
    i=get_next();
    scanf("%s",dum);
    scanf(" 10^%d ",&k);
    j=get_next();

    in[i][j]=k;
    in[j][i]=-k;
  }

  n = number; dame=0;
  rep(k,n){
    rep(i,n) rep(j,n){
      if(in[i][j]==INF && in[i][k]!=INF && in[k][j]!=INF) in[i][j] = in[i][k]+in[k][j];
      if(in[i][j]!=INF && in[i][k]!=INF && in[k][j]!=INF) if(in[i][j] != in[i][k]+in[k][j]) dame=1;
    }
    if(dame) break;
  }

  if(!dame) puts("Yes"); else puts("No");

  return 0;
}
E. トーマス・ライトの憂鬱 (CODE)

本番に提出した,C言語によるスパゲッティなコードです.
Accepted, 0.02sec.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

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

int main(){
  int i,j,k,l,m,n;
  int x[10000], y[10000];
  int x1, x0, y1, y0;
  int x_st, x_ed, y_st, y_ed;

  scanf("%d",&n);
  rep(i,n) scanf("%d",x+i);
  rep(i,n) scanf("%d",y+i);

  x1=x0=y1=y0=0;
  intSort(x,n); intSort(y,n);
  x_st=y_st=0;
  x_ed=y_ed=n-1;

  for(;;){
    int fg=0;
    while(x_st <= x_ed && x[x_st] == y1) x_st++, x0++, fg++;
    while(y_st <= y_ed && y[y_st] == x1) y_st++, y0++, fg++;
    while(x_st <= x_ed && x[x_ed] == n-y0) x_ed--, x1++, fg++;
    while(y_st <= y_ed && y[y_ed] == n-x0) y_ed--, y1++, fg++;
    if(!fg) break;
  }

  if(x_st>x_ed && y_st>y_ed) puts("Yes"); else puts("No");

  return 0;
}
F. UTF-8 (CODE)

本番に提出した,C言語によるスパゲッティなコードです.
Accepted, 0.01sec.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define M 1000000

#define ll long long

int n;
int dp[120000];
char in[120000][10];

int is_ok(char depth[],char hoge[],int len){
  int i;
  rep(i,len){
    if(depth[i]=='x') continue;
    if(depth[i]!=hoge[i]) return 0;
  }
  return 1;
}

int solve(int now){
  int i,j,k;
  ll res=0, mul;

  if(dp[now]>=0) return dp[now];
  
  if( now+1<=n && is_ok(in[now],"0",1) ){
    mul=1;
    REP(i,1,8) if(in[now][i]=='x') mul = (mul*2)%M;
    res += solve(now+1) * mul;
    res %= M;
  }

  if( now+2<=n && is_ok(in[now],"110",3) && is_ok(in[now+1],"10",2) ){
    mul=1;
    REP(i,3,7) if(in[now][i]=='x')   mul = (mul*2)%M;
    if( is_ok(in[now]+3,"0000",4) ) mul = (mul+M-1)%M;
    REP(i,7,8) if(in[now][i]=='x')   mul = (mul*2)%M;
    REP(i,2,8) if(in[now+1][i]=='x') mul = (mul*2)%M;
    res += solve(now+2) * mul;
    res %= M;
  }

  if( now+3<=n && is_ok(in[now],"1110",4) && is_ok(in[now+1],"10",2) && is_ok(in[now+2],"10",2) ){
    mul=1;
    REP(i,4,8) if(in[now][i]=='x')   mul = (mul*2)%M;
    REP(i,2,3) if(in[now+1][i]=='x') mul = (mul*2)%M;
    if( is_ok(in[now]+4,"0000",4) && is_ok(in[now+1]+2,"0",1 ) ) mul = (mul+M-1)%M;
    REP(i,3,8) if(in[now+1][i]=='x') mul = (mul*2)%M;
    REP(i,2,8) if(in[now+2][i]=='x') mul = (mul*2)%M;
    res += solve(now+3) * mul;
    res %= M;
  }

  if( now+4<=n && is_ok(in[now],"11110",5) && is_ok(in[now+1],"10",2) && is_ok(in[now+2],"10",2) && is_ok(in[now+3],"10",2) ){
    mul=1;
    REP(i,5,8) if(in[now][i]=='x')   mul = (mul*2)%M;
    REP(i,2,4) if(in[now+1][i]=='x') mul = (mul*2)%M;
    if( is_ok(in[now]+5,"000",3) && is_ok(in[now+1]+2,"00",2 ) ) mul = (mul+M-1)%M;
    REP(i,4,8) if(in[now+1][i]=='x') mul = (mul*2)%M;
    REP(i,2,8) if(in[now+2][i]=='x') mul = (mul*2)%M;
    REP(i,2,8) if(in[now+3][i]=='x') mul = (mul*2)%M;
    res += solve(now+4) * mul;
    res %= M;
  }

  return dp[now] = res;
}

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

  scanf("%d",&n);
  rep(i,n) scanf("%s",in[i]);

  rep(i,n) dp[i]=-1; dp[n]=1; REP(i,n+1,n+10) dp[i]=0;

  k = solve(0);
  printf("%d\n",k);

  return 0;
}
G. 天体観測 (CODE)

本番に提出した,C言語によるスパゲッティなコードです.
Accepted, 0.02sec.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int GCD(int a,int b){int r; while(a){r=b; b=a; a=r%a;} return b;}
int LCM(int a,int b){return a/GCD(a,b)*b;}

int isLeapYear(int y){if(y%400==0)return 1;if(y%100==0)return 0; if(y%4==0)return 1; return 0;}
int numberOfDaysInMonth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
char *nameDayOfWeek[7]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
void nextDay(int *year,int *month,int *day){
  if((*day) < numberOfDaysInMonth[*month] || ((*month)==2 && isLeapYear(*year) && (*day)==28)){
    (*day)++; return;
  }
  (*day)=1; if((*month)==12) (*year)++, (*month)=1; else (*month)++;
}



#define EPS 1e-10
#define PI 3.141592653589793238462
typedef struct struct_point3{double x,y,z;}pnt3;
typedef struct struct_line3{pnt3 a,b;}line3;
typedef struct struct_plane3{pnt3 a,b,c;}plane3;
typedef struct struct_sphere{pnt3 c; double r;}sphere;

int doubleSign(double a){if(a>EPS) return 1; if(a<-EPS) return -1; return 0;}
int pnt3Sign(pnt3 a){
  int i = doubleSign(a.x); if(i) return i;
      i = doubleSign(a.y); if(i) return i;
  return doubleSign(a.z);
}

pnt3 pnt3Plus(pnt3 a,pnt3 b)             {a.x+=b.x; a.y+=b.y; a.z+=b.z; return a;}
pnt3 pnt3Minus(pnt3 a,pnt3 b)            {a.x-=b.x; a.y-=b.y; a.z-=b.z; return a;}
pnt3 pnt3MultipleDouble(pnt3 a,double k) {a.x*=k;   a.y*=k;   a.z*=k;   return a;}

double pnt3Length(pnt3 a){return sqrt(a.x*a.x+a.y*a.y+a.z*a.z);}
double pnt3Length2(pnt3 a){return a.x*a.x+a.y*a.y+a.z*a.z;}
double pnt3Distance(pnt3 a,pnt3 b){return pnt3Length(pnt3Minus(a,b));}
double pnt3Distance2(pnt3 a,pnt3 b){return pnt3Length2(pnt3Minus(a,b));}

pnt3 pnt3Normalize(pnt3 a){return pnt3MultipleDouble(a,1.0/pnt3Length(a));}
double pnt3InnerProduct(pnt3 a,pnt3 b){return a.x*b.x+a.y*b.y+a.z*b.z;}

pnt3 pnt3Generator(double x,double y,double z){pnt3 res; res.x=x; res.y=y; res.z=z; return res;}

pnt3 rotX(pnt3 p, double th){ /* Y→Z */
  pnt3 res;
  res.x = p.x;
  res.y =  cos(th) * p.y - sin(th) * p.z;
  res.z =  sin(th) * p.y + cos(th) * p.z;
  return res;
}

pnt3 rotY(pnt3 p, double th){ /* Z→X */
  pnt3 res;
  res.x =  cos(th) * p.x + sin(th) * p.z;
  res.y = p.y;
  res.z = -sin(th) * p.x + cos(th) * p.z;
  return res;
}

pnt3 rotZ(pnt3 p, double th){ /* X→Y */
  pnt3 res;
  res.x =  cos(th) * p.x - sin(th) * p.y;
  res.y =  sin(th) * p.x + cos(th) * p.y;
  res.z = p.z;
  return res;
}

#define MMR   (43.2)
#define ROOTs ((1+1/365.24)*360)
int main(){
  int i,j,k,l,m,n,q;
  double a[10000], b[10000];
  pnt3 p[10000];
  char name[1000];
  double tm;

  int month, day, hour, minite;
  int yy=2012, mm=1, dd=1;

  scanf(" %d/%d %d:%d ",&month,&day,&hour,&minite);
  tm=0;

  while(mm!=month || dd!=day) tm+=1, nextDay(&yy,&mm,&dd);
  tm += (hour*60+minite)/(double)(24*60);

  scanf("%d",&q);
  while(q--){
    scanf("%s%d",name,&n);
    rep(i,n) scanf("%lf%lf",a+i,b+i);

    rep(i,n) a[i] *= PI / 180, b[i] *= PI / 180;
    rep(i,n){
      p[i].x = cos(a[i]) * cos(b[i]);
      p[i].y = sin(a[i]) * cos(b[i]);
      p[i].z = sin(b[i]);
    }

    rep(i,n) p[i] = rotY(p[i], MMR*PI/180);
    rep(i,n) p[i] = rotX(p[i], tm*ROOTs*PI/180);
    rep(i,n) p[i] = rotY(p[i],-MMR*PI/180);

    rep(i,n) if(p[i].z<0) break;
    if(i==n) puts(name);
  }

  return 0;
}
H. 迷い猫、走った (CODE)

本番に提出した,C言語によるスパゲッティな嘘コードです.
Accepted, 0.81sec.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

void intSort(int d[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}intSort(d,i);intSort(d+j+1,s-j-1);}
void intIntSort(int d[],int m[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}

int ab(int x){if(x<0)return -x; return x;}

int m,n;
int neko[1200], num[1200];
int hako[1200];
int dist[1200][1200];
int dp[1200][1200];

int solve(int a,int b){
  int i,j,k,res=2000000000,tmp=0;
  int st;

  if(dp[a][b]>=0) return dp[a][b];
  rep(st,n) if(dist[st][a] > dist[st][b]) break;

  REP(i,b+1,m){
    while(st<n && dist[st][b] <= dist[st][i]) tmp+=num[st++];
    k=solve(b,i);
    if(k<tmp) k=tmp;
    if(res>k) res=k;
    if(k==tmp) break;
  }

  while(st<n) tmp += num[st++];
  if(res > tmp) res = tmp;

  return dp[a][b]=res;
}

int main(){
  int i,j,k,l,tmp;
  int res;

  scanf("%d%d",&n,&m);
  rep(i,n){
    scanf("%d%d%d",&j,&k,&l);
    neko[i]=j; num[i]=l;
  }
  intIntSort(neko,num,n);

  rep(i,m) scanf("%d",hako+i);
  intSort(hako,m);

  res=0; rep(i,n) res += num[i];

  rep(i,n) rep(j,m) dist[i][j] = ab(neko[i]-hako[j]);
  
  rep(i,m) rep(j,m) dp[i][j]=-1;
  REP(i,1,m){
    k = solve(0,i);
    tmp=0; rep(j,n) if(dist[j][0] <= dist[j][i]) tmp+=num[j];
    if(k<tmp) k=tmp;
    if(res > k) res = k;
  }

  printf("%d\n",res);

  return 0;
}
I. 盗まれた宝石 (CODE)

本番に提出した,C言語によるスパゲッティなコードです.
Accepted, 0.03sec.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int is_same(char a[],char b[],int len){
  int i;
  rep(i,len) if(a[i]!=b[i]) return 0;
  return 1;
}

int x,y;
int dist[51][51][12][12];
int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
int q[10000000], q_st, q_size;
char *dir="URDL";

char mp[77][77];
int n;
char pat[77][77]; int len[77];
int edge[22][22][4];

char tmp[1000];

int main(){
  int i,j,k,l,m,mx;
  int a,b,c;
  int res=-1;

  int sx,sy, ex,ey, nx,ny, na,nb, dd;

  scanf("%d%d",&x,&y);
  rep(i,x) scanf("%s",mp[i]);
  scanf("%d",&n);
  rep(i,n) scanf("%s",pat[i]);

  rep(i,n){
    for(k=0;;k++) if(pat[i][k]<' ') break;
    len[i]=k;
  }

  if(n==0){
    n++;
    pat[0][0]='Q';
    len[0]=1;
  }

  rep(i,n) rep(j,len[i]){
    rep(k,j) tmp[k]=pat[i][k];
    rep(k,4){
      tmp[j]=dir[k];
      a=b=c=0;
      rep(l,n) for(m=1;m<=len[l] && m<=j+1; m++){
        if(!is_same(pat[l], tmp+j+1-m, m)) continue;
        if(m==len[l]) c=1;
        if(b<m) a=l, b=m;
      }
      edge[i][j][k] = a*1000 + b;
      if(c) edge[i][j][k]=-1;

/*      printf("%d %d %d -> %d\n",i,j,k,edge[i][j][k]);*/
    }
  }

  rep(i,x) rep(j,y){
    if(mp[i][j]=='S') sx=i, sy=j;
    if(mp[i][j]=='G') ex=i, ey=j;
  }

  rep(i,x) rep(j,y) rep(k,n) rep(l,len[k]) dist[i][j][k][l]=-1;
  dist[sx][sy][0][0]=0;

  q_st=0; q_size=1;
  q[0] = (sx*y+sy)*10000 + 0;

  while(q_size){
    a = q[q_st]/10000; b = q[q_st]%10000; q_st++; q_size--;
    sx = a/y; sy=a%y; i=b/1000; j=b%1000;
    if(sx==ex && sy==ey){ res=dist[sx][sy][i][j]; break; }
    rep(k,4) if(edge[i][j][k]>=0){
      nx = sx+dx[k]; ny = sy+dy[k];
      if(nx<0||ny<0||nx>=x||ny>=y) continue;
      if(mp[nx][ny]=='#') continue;
      na = edge[i][j][k]/1000; nb = edge[i][j][k]%1000;
      if(dist[nx][ny][na][nb]>=0) continue;
      dist[nx][ny][na][nb] = dist[sx][sy][i][j]+1;
      q[q_st+q_size++] = (nx*y+ny)*10000 + na*1000+nb;
    }
  }

  printf("%d\n",res);

  return 0;
}
K. ワープホール (CODE)

本番に提出した,C言語によるスパゲッティなコードです.
Accepted, 1.39sec.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define M 1000000007
#define N 1000000000LL

ll pw(ll a,ll k){
  ll r;
  if(k==0) return 1;
  r = pw(a,k/2);
  r = (r*r)%M;
  if(k%2) r=(r*a)%M;
  return r;
}

ll fact[210000], inv[210000];

ll comb(int a,int b){
  ll res = 1;
  res = (res*fact[a])%M;
  res = (res*inv[b])%M;
  res = (res*inv[a-b])%M;
  return res;
}

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

ll p[2100], xy[2100], ind[2100];

int main(){
  int i,j,k,l,m,n,node;
  int x,y;
  int dx, dy, nx, ny;

  fact[0]=1; REP(i,1,210000) fact[i]=(fact[i-1]*i)%M;
  rep(i,210000) inv[i]=pw(fact[i],M-2);

  scanf("%d%d%d",&x,&y,&n);
  x--; y--;
  rep(m,n){
    scanf("%d%d%d%d",&i,&j,&k,&l);
    i--; j--; k--; l--;
    xy[2*m+0] = i*N + j;
    xy[2*m+1] = k*N + l;
  }

  for(;;){
    int fg=0;
    rep(i,n) rep(j,n) if(xy[2*i+1]==xy[2*j]){
      xy[2*i+1] = xy[2*j+1]; fg=1;
    }
    if(!fg) break;
  }
  
  rep(i,2*n+1) ind[i]=i, p[i]=0;
  xy[2*n] = x*N+y;

  intIntSort(xy,ind,2*n);

  node = 2*n+1;
  rep(i,node){
    if(ind[i]%2==1) continue;
    nx = xy[i]/N; ny = xy[i]%N;
    p[i] = (p[i] + comb(nx+ny,nx))%M;
    rep(j,i){
      dx = nx - xy[j]/N;
      dy = ny - xy[j]%N;
      if(dx<0 || dy<0) continue;
      if(ind[j]%2==0) p[i] -= p[j] * comb(dx+dy,dx);
      else            p[i] += p[j] * comb(dx+dy,dx);
      p[i] %= M;
      if(p[i]<0) p[i] += M;
    }
    if(ind[i]%2==0) REP(j,i+1,node) if(ind[i]+1==ind[j]){
      p[j] = (p[j]+p[i])%M;
    }

/*    printf("%d %d : %d : %lld\n",nx,ny,i,p[i]);*/
  }

  printf("%d\n",(int)p[node-1]);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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