Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Facebook Hacker Cup 2011 Qualification Round B問題 - Peg Game (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Qualification Round B問題
Facebook Hacker Cup 2011 Qualification Roundの参加記録

問題概要

ボールを落とす.パチンコみたいに,pegに当たると左下か右下に当確率で移動する.
pegがなければ真下に落ちる.
一番下のある場所に落とす確率を最大化するためには,一番上のどの場所から落とせば良いか,また最大値を求める問題.
グリッドのサイズは100*100ぐらい以下.

解法

DPする.ここからゴールに辿りつける確率を各セルについて覚えておく.

C言語のスパゲッティなコード
#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 EPS 1e-14

int x,y,g;
char mp[102][222];
double dp[102][222];

double solve(int a,int b){
  int i,j,k;
  double res=0, per=0;

  if(dp[a][b] > -1) return dp[a][b];
  if(a==x-1){
    if(2*g+1==b) res += 1;
    return dp[a][b] = res;
  }

  if(mp[a+1][b]==0) return dp[a][b] = solve(a+1,b);

  if(mp[a+1][b-1]==0) res += solve(a+1,b-1), per += 1;
  if(mp[a+1][b+1]==0) res += solve(a+1,b+1), per += 1;

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

int main(){
  int i,j,k,l,m,n;
  int size;
  int res; double mx, tmp;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d%d%d",&x,&y,&g,&n);
    rep(i,x) rep(j,2*y-1) mp[i][j]=1;
    rep(i,x) for(j=1+i%2;j<2*y-2;j+=2) mp[i][j]=0;

    while(n--){
      scanf("%d%d",&i,&j);
      mp[i][i%2+j*2] = 0;
    }

/*    rep(i,x){ rep(j,2*y-1) putchar('0'+mp[i][j]); puts(""); } puts("");*/

    rep(i,x) rep(j,2*y+1) dp[i][j] = -100;
    mx = -100;
    rep(j,y-1){
      tmp = solve(0,2*j+1);
      if(mx < tmp-EPS) mx = tmp, res = j;
    }

    printf("%d %.6lf\n",res,mx+EPS);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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