Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM498 DIV1 HARD (1000pt)
Problem Statement
SRM498 DIV1 自分の参加記録

問題概要

最初(0,0)にいる狐が,ちょうどR回 (1600以下) のジャンプで (Tx,Ty) に移動するジャンプパターンの数をmod 10007で求める問題.
MxとMyが与えられて,1回のジャンプでは,x軸の正方向に0セル以上Mxセル以下移動,y軸の正方向に0セル以上Myセル以下移動しなければいけない.
現在のセルにとどまるジャンプは許されない.
また,要素数50以下,各要素10の倍数の配列badが与えられて,x軸方向にも,y軸方向にも両方ともbad[k]だけ移動するようなジャンプは許されない.
Tx, Tyは0以上800以下,Mx, Myも800以下.

解法

badに0を加えることで,現在位置に留まることができないという条件を考えないで良くなる.
まず,badが空の場合について考える.
これは,x座標とy座標独立に考えることができて,それはTxにたどり着くパターン数はDPで数えることができる.
 dp[現在までのジャンプ回数][現在のx座標] = ここに辿り着く経路の数
愚直に書けば,O(R*Tx*Mx)でTLEになるが,途中までの和を記録して,上手く計算することでO(R*Tx)で書ける.
badがある場合は,包除原理を利用すれば良い.
 すべての場合 - badを1回使って,残りは自由な場合 + badを2回使って,残りは自由の場合 - …
badをk回使って,斜め方向に何セル進む方法がいくつあるか,というのもDPで求める.

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 10007

int dp[2000][1000],sum[2000];

int solve1D(int g,int can,int R){
  int i,j,k;

  g++;
  rep(i,g) dp[0][i]=0; dp[0][0]=1;
  rep(k,R){
    sum[0]=0; rep(i,g) sum[i+1]=sum[i]+dp[k][i];
    rep(i,g){
      dp[k+1][i] = sum[i+1];
      if(i-can >= 0) dp[k+1][i] -= sum[i-can];
      dp[k+1][i] %= M;
      if(dp[k+1][i]<0) dp[k+1][i]+=M;
    }
  }

  return dp[R][g-1];
}


int comb[2000][2000];
int dpx[2000][1000], dpy[2000][1000];
int dpb[1000], next[1000];

class FoxJumping {
public:
int getCount(int Tx, int Ty, int Mx, int My, int R, vector <int> bad) {
  int i,j,k,mx,a,b;
  int res = 0, add;

  bad.push_back(0);

  comb[0][0]=1; REP(j,1,2000) comb[0][j]=0;
  REP(i,1,2000){ comb[i][0]=1; REP(j,1,2000) comb[i][j]=(comb[i-1][j-1]+comb[i-1][j])%M; }

  a=solve1D(Tx,Mx,R);
  rep(i,R+1) rep(j,Tx+1) dpx[i][j]=dp[i][j];
  b=solve1D(Ty,My,R);
  rep(i,R+1) rep(j,Ty+1) dpy[i][j]=dp[i][j];

  res = (a*b)%M;

  mx = min(Tx,Ty) + 1;
  dpb[0]=1; REP(i,1,mx) dpb[i]=0;
  rep(k,R){
    for(i=0;i<mx;i+=10) next[i]=0;
    for(i=0;i<mx;i+=10) rep(j,bad.size()){
      a = i + bad[j];
      if(a>=mx) continue;
      next[a] += dpb[i];
    }
    for(i=0;i<mx;i+=10){
      dpb[i] = next[i]%M;
      if(dpb[i]<0) dpb[i]+=M;

      add = (dpb[i] * comb[R][k+1])%M;
      add = (add * dpx[R-k-1][Tx-i])%M;
      add = (add * dpy[R-k-1][Ty-i])%M;
      
      if( (k+1)%2 ) add = (M-add)%M;
      res = (res+add)%M;
    }
  }

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

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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