Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM472 DIV2 HARD - RectangularIsland (この記事を編集する[管理者用])

Source

TopCoder SRM472 DIV2 HARD (1000pt)
Problem Statement

問題概要

width*heightのマス目の盤面がある.
最初いる位置と,ターン数が与えられる.
各ターン,上下左右を当確率で選んでそっちの方向に向かう.
盤面の外に一度も出ない確率を求める確率.
width, heightは1000以下,ターン数は5000以下.

解法

上下に動く回数と,左右に動く回数を固定して,全パターン考えて,足し合わせる.
上下に動く回数が定まっていれば,1次元ごとに考えて,包除原理を用いて,盤面からはみ出す確率を求める.
1次元ごとに考える場合は,DPすれば良い.
DPはkターン目に,座標mにいる確率をメモしておく.

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

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

double memo[1200], next[1200];

void solve(int x,int sx,int steps,double res[]){
  int i,j,k,tm;

  res[0]=0;
  rep(i,x+2) memo[i]=0; memo[sx+1]=1;

  REP(tm,1,steps+1){
    rep(i,x+2) next[i]=0;
    next[0] = memo[0];
    next[x+1] = memo[x+1];
    REP(i,1,x+1){
      next[i-1] += memo[i]/2;
      next[i+1] += memo[i]/2;
    }
    rep(i,x+2) memo[i]=next[i];
    res[tm] = memo[0]+memo[x+1];
  }
}

double dp1[6000], dp2[6000];

class RectangularIsland {
public:
double theProbablity(int width, int height, int x, int y, int steps) {
  int i,j,k;
  double res=0;
  double f[6000], per, l2;

  solve(width,x,steps,dp1);
  solve(height,y,steps,dp2);

  l2 = log(2) * steps;
  f[0]=0; REP(i,1,6000) f[i]=f[i-1]+log(i);

  rep(k,steps+1){
    per = f[steps] - f[k] - f[steps-k] - l2;
    per = exp(per);

    res += per * ( dp1[k] + dp2[steps-k] - dp1[k]*dp2[steps-k] );
  }

  return 1-res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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