Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

 | 

2014-06-07

SRM 614 Hard (TorusSailing)

23:42

editorial: http://apps.topcoder.com/wiki/display/tc/SRM+614

参考: http://nkl.cc.u-tokyo.ac.jp/08s/CS01/GaussSeidel.pdf

http://petr-mitrichev.blogspot.jp/2014/03/this-week-in-competitive-programming_30.html

問題

N * M のトーラス上で,右か上に 1/2 の確率でランダムウォークする.(X,Y) にたどりつくまでの歩数の期待値を求めよ.

制約
  • N, M <= 100

解法

まともな解法は,editorial を参照.アイデア: https://twitter.com/ogiekako/status/449972273940660225

ここでは,反復法で解くやりかたを書く.あまり詳しくないので,補足など下さると嬉しいです.

結局,Ax = b という形の線形連立方程式の解を求めれば良い.ただし,方程式と,変数の数が最大 10000 個になるので,Gaussian elimination では解けない.そこで反復法を使う.

まず x0 =0 として初期化する.

Jacobi 法では,ベクトル x_i から x_{i+1} を計算する.これだと収束が遅くてダメ.

Gauss-Seidel 法では,x_{i,j} を計算したらすぐに,x_{i,j+1} の計算でその値を使う.

これによって,収束が速くなって(Petrブログによると50-100倍),7000回まわせば正しい解がでるようになる.

どういう行列だと収束が速いんだろうか?

 |