スプリング・タイル (AOJ 2336)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2336

問題

略

解法

各マスからゴール・バネまでの距離を計算しておいて、バネに乗った後のゴールまでの距離の期待値を2分探索で求める。答えはかなり大きくなるので注意。あと誤差が厳しいのでlong doubleを使うか、ハフマン符号のように小さい数値から足していくこと。