Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #24 D問題 - Broken robot (この記事を編集する[管理者用])

Source

Codeforces Beta Round #24 D問題
Problem description
Beta Round #24の自分の参加記録

問題概要

1000*1000以下のグリッドのある場所に最初ロボットがいる.
時間1後,
 今の場所,ひとつ下,ひとつ右,ひとつ左
のうち,盤面の外に飛び出さない方向を1つ選んで当確率に移動する.
一番下の行についたら止まる.
止まるまでの時間の期待値を求める問題.

解法

ある行にいる場合の,終了までの時間の期待値がすべて分かっているとすると,
次の行にいる場合の,終了までの時間の期待値は,行列サイズ1000以下の3重対角の連立一次方程式を解けば求まる.
3重対角なのでO(行列サイズ)で解ける.
以下のコードは,収束するまで反復しても要求精度をギリギリ満たせた.

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)

int x,y,sx,sy;
double dp[1100][1100], tmp;

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

int main(){
  int i,j,k,l,m,n,loop,loop_mx;
  double per;

  scanf("%d%d%d%d",&x,&y,&sx,&sy);
  sx--; sy--;

  if(y==1){ printf("%.10lf\n",2.0*(x-1-sx)); return 0; }

  if(y==1) per = 3;
  else     per = (3+3+4*(y-2))/(double)y;
  
  rep(i,x) rep(j,y) dp[i][j]=(x-1-i)*per;

  loop_mx = 90000000 / x / y;

  for(i=x-2;i>=0;i--){
    rep(loop,loop_mx){
      double err=0;
      rep(j,y){
        if(j==0)        tmp = (dp[i+1][j] + dp[i][j] + dp[i][j+1])/3;
        else if(j==y-1) tmp = (dp[i+1][j] + dp[i][j] + dp[i][j-1])/3;
        else            tmp = (dp[i+1][j] + dp[i][j] + dp[i][j-1] + dp[i][j+1])/4;
        tmp += 1;
        err += ab(dp[i][j]-tmp);
        dp[i][j]=tmp;
      }
    }
  }

  printf("%.10lf\n",dp[sx][sy]);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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