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: 2017年09月21日05時05分52秒
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)

ログイン: