Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM563 DIV1 HARD - CoinsGame (この記事を編集する[管理者用])

Source

TopCoder SRM563 DIV1 HARD (950pt)
Problem Statement

問題概要

40*40以下のグリッドが与えられる.各セルは空か障害物がおいてある.
空のセルにはコインを置くことができる.
その後,グリッドを上下左右に一瞬傾けるという操作を何回でも行うことができる.そうすると,
 すべてのコインが傾けた向きに1だけ移動する
 ただし,移動先が障害物なら現在の位置に残る
 また,移動先がグリッドの外ならグリッドから落ちてコインがなくなる
いくらか操作した後,1枚以上のコインが落ちて,1枚以上のコインがグリッドに残ってなければいけない.
それが可能なコインの置き方は何通りあるかをmod 1000000009で求める問題.

解法

全部の置き方から,置いたコインが全部同時に落ちるしかないという場合の数を引く.
それは,それぞれの空のセルをグループに分ければ良い.
各グループは,どんな操作の連続でも,同じタイミングに落ちる.(もしくは落ちれない)
グループ分けには,ハッシュを使った.
最初全部のセルのハッシュ値を0,グリッドの外のハッシュ値を1として,
グリッドの面積回ぐらい,各セルについて
 上下左右に傾けた時に移動する場所4箇所のハッシュを使って,新しいハッシュ値に置き換える
という操作を同時に行う.
すると,どうやっても同時に落ちる場所のみが同じハッシュ値になる.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

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

#define M 1000000009
#define ll long long
#define ull unsigned ll

#define N 4

ull D[4], DM[10];
ull hs[10][41][41], next[10][41][41];

int is_prime(int n){
  int i;
  for(i=2;i*i<=n;i++) if(n%i==0) return 0;
  return 1;
}

ll pw(ll a,ll b, ll md){
  ll r;
  if(!b) return 1;
  r = pw(a,b/2,md);
  r = (r*r)%md;
  if(b%2) r = (r*a)%md;
  return r;
}

class CoinsGame {
public:
int ways(vector <string> in) {
  int i, j, k, m, x, y, loop;
  int dx[4] = {-1,1,0,0}, dy[4]={0,0,-1,1};
  int ni, nj, d, a, b;
  int st[51][51];
  ll res = 0;

  x = in.size();
  y = in[0].size();

  rep(i,4) D[i] = 1007 + 107*i*i*i;
  k = 0;
  for(i=1000000000;;i++) if(is_prime(i)){
    DM[k++] = i;
    if(k==N) break;
  }

  rep(k,N) rep(i,x) rep(j,y) hs[k][i][j] = 0;

  rep(loop,1601){
    rep(k,N) rep(i,x) rep(j,y) next[k][i][j] = 0;
    
    rep(k,N) rep(i,x) rep(j,y){
      rep(d,4){
        ni = i+dx[d]; nj = j+dy[d];
        if(ni<0||nj<0||ni>=x||nj>=y){ next[k][i][j] += D[d]; next[k][i][j] %= DM[k]; continue; }
        if(in[ni][nj]=='#') ni = i, nj = j;
        next[k][i][j] += D[d] * hs[k][ni][nj];
        next[k][i][j] %= DM[k];
      }
    }
    
    rep(k,N) rep(i,x) rep(j,y) hs[k][i][j] = next[k][i][j];
  }

/*  rep(k,N) if(k==0){ 
    puts("");
    rep(i,x){ rep(j,y) printf("%llu ",hs[k][i][j]); puts(""); }
  }*/

  k = 0;
  rep(i,x) rep(j,y) if(in[i][j]=='.') k++;
  res = pw(2, k, M) - 1;
/*  printf("total %d\n",k);*/

  rep(i,x) rep(j,y) st[i][j] = 0;
  rep(i,x) rep(j,y) if(in[i][j]=='.' && st[i][j]==0){
    k = 0;
    rep(a,x) rep(b,y) if(in[a][b]=='.' && st[a][b]==0){
      rep(m,N) if(hs[m][i][j]!=hs[m][a][b]) break;
      if(m<N) continue;
      k++; st[a][b]=1;
    }
    res -= pw(2, k, M) - 1;
/*    printf("per %d (%d %d)\n",k,i,j);*/
  }

  res %= M;
  if(res < 0) res += M;

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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