Yuki 75 回数の期待値の問題 ( DP, Gauss Seidel )

No.75 回数の期待値の問題 - yukicoder
古寺いろはのサブミ見て勉強になった。
漸化式が状態を互いに参照しまわりそうで DAG になれそうにない時は連立方程式に書き換えてとけばいいことですが、もっと簡単な方法で近似値が求められる。その方法とはただ愚直にループで何度も漸化式で更新するだけという話で、答えにかなり早く収斂して実用なものらしい。ガウスゼイデル法と呼ぶらしい。

この問題にも全く同じ方法で通せるらしい ( 問題文の中のイメージが壊れたようなので、kmjp さんのブログからみてください）。

int K;

void init(){
  cin >> K;
}

vd dp;

void preprocess(){
  dp = vd( K );
  for( int i = 0; i < 1000; ++i )
    for( int j = 0; j < K; ++j ){
      double s = 0.0;
      for( int k = 1; k <= 6; ++k ){
        if( j + k < K )
          s += dp[ j + k ] / 6;
        if( j + k > K )
          s += dp[ 0 ] / 6;
      }
      dp[ j ] = s + 1.0;
    }
}

void solve(){
  cout << fixed << setprecision( 6 ) << dp[ 0 ] << endl;
}