2014年04月27日05時25分35秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．

TopCoderOpen Algorithm 2014 Round 1C HARD - RedPaint

Source

TopCoderOpen Algorithm 2014 Round 1C HARD (950pt)
Problem Statement

問題概要

無限に長い一直線上に配置されたマスのある場所にロボットがいる．
このロボットが $N$ ステップだけ動く．
各ステップでは，左右等確率に選び，そっちに $1$ マス移動する．
ロボットが訪れるマス（初期位置も含む）の期待値を求める問題．

解法

DPする．
状態を（現在何ステップ行ったか，ロボットが訪れた区間の幅，今ロボットはその区間の左から何マス目にいるか）と取り，その確率を計算していく．
計算時間量は $O(N^3)$．現在何ステップ行ったかは前のステップだけ覚えておけば良いので，空間計算量は $O(N^2)$ で良い．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

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

double dp[510][510], nx[510][510];

class RedPaint {
public:
double expectedCells(int N) {
  int i, j, k;
  int ni, nj;
  double res;

  rep(i,N+2) rep(j,N+2) dp[i][j] = 0;
  dp[0][1] = 1;

  rep(k,N){
    rep(i,N+2) rep(j,N+2) nx[i][j] = 0;
    rep(i,N+2) rep(j,N+2){
      ni = i-1; nj = j;
      if(ni < 0) ni++, nj++;
      if(ni == nj) nj++;
      nx[ni][nj] += dp[i][j] / 2;

      ni = i+1; nj = j;
      if(ni < 0) ni++, nj++;
      if(ni == nj) nj++;
      nx[ni][nj] += dp[i][j] / 2;
    }
    rep(i,N+2) rep(j,N+2) dp[i][j] = nx[i][j];
  }

  res = 0;
  rep(i,N+2) rep(j,N+2) res += j * dp[i][j];

  return res;
}

}

Current time: 2024年04月17日01時45分49秒
Last modified: 2014年04月27日05時25分35秒 (by laycrs)
Tags: Competitive_Programming TopCoder TopCoderOpen TCO_Algorithm TCO_Algorithm_2014 TCO_Algorithm_2014_1C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：