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

TopCoder SRM614 DIV1 HARD - TorusSailing

Source

TopCoder SRM614 DIV1 HARD (1000pt)
Problem Statement

問題概要

$N \times M$ 個のセルがあって，各セルは $(x,y),\;\;0 \leq x \leq N-1,\ 0 \leq y \leq M-1$ で表される．
以下のルールに従って移動するとき，最初セル $(0,0)$ にいて，セル $(G_x, G_y)$ に辿り着くまでの時間の期待値を求める問題．
ルールは，ゴールのセルにいなく，今のセルが $(x,y)$ であれば，同確率で $(x+1\ {\rm mod}\ N,\ y)$ か $(x,\ y+1\ {\rm mod}\ M)$ に移動する．

解法

各セルにゴールするまでの期待値を計算（初期値は適当にしておいて）して，収束するまで（あるいは制限時間いっぱい）回す．
誤差の伝達の方向を考えて，ループの順番を適切に選ぶ．
以上は，コンテスト終了後，こんなシンプルな解法が通るとは思わなかった，とメッセージが流れたもの．
想定解法は，おそらく，途中のセルを端折って，$N+M$ セルぐらいのみを考え，連立一次方程式を立ててガウスジョルダンみたい．
条件数の見積もりとかはよくわからないが，答えは最大でも $11700$ 程度でうまくいきそう．

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

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

class TorusSailing {
public:
double expectedTime(int N, int M, int X, int Y) {
  int i, j, k, loop;
  static double dp[101][101];
  double res;

  rep(i,N) rep(j,M) dp[i][j] = N*M;
  dp[X][Y] = 0;

  rep(loop,12000){
    for(i=N-1;i>=0;i--) for(j=M-1;j>=0;j--){
      if(i==X && j==Y) continue;
      dp[i][j] = (dp[(i+1)%N][j] + dp[i][(j+1)%M]) * 0.5 + 1.0;
    }
  }

  res = dp[0][0];
  return res;
}

}

Current time: 2024年04月20日09時10分18秒
Last modified: 2014年03月31日19時25分46秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM614 SRM_Div1_Hard Linear_Equation
トップページに戻る

Logged in as: unknown user (not login)

ログイン：