公式解説では後ろから再帰的に求めていっている。前からでもDPできる。あり、True,Falseそれぞれ1通りずつ。2*DP[i-1][1]という遷移を実装すればよい。操作は、1,2が回転移動、3,4が平行移動+対称移動の操作となっている。いうベクトルに、操作ごとに所定の行列をかけることで、操作後の座標を得られるような性質を持つ。放り込んでやれば複数回の操作をまとめて行ったのと同じことになる。実装では、行列をスムーズに扱えるかちょっと自信がなかったので、単純化して実装した。いずれかは両方0になっている。どちらが0かフラグ」を含む5つの値を管理することで、行列と同様の情報を持たせた。マス目までにかかる回数期待値、みたいなのを行いそうではあるが、一筋縄ではいかない。循環DPとその解消策これは循環する要素のあるDPとなっている。必要このようなDPは埋め方に工夫が必要になる。誤差が比較的ゆるゆるでもOKループごとに指数的に確率は低くなっていき、逆にルーレットを回す回数は線形でしか増加しないので、収束することが明らかなので、確率が十分に低くなり、期待値に与える影響が小さくなるまで、繰り返し計算する、という方針をとる。結果的に前者と似たような実装が必要になったので、前者の方がスマートと思う。(解法2に、前者の方法も書いた)高速化の必要性さて、ではどれくらい繰り返せばよいかというと、スタートに戻る確率が高いほど、期待値に与える影響が小さくなるスピードが遅くなる。10個のスタートに戻るマスが2つおきにある場合など。約99.99987%でスタートに戻る。回スタートに戻ってもまだゴールできない確率は88%近くあり、期待値に与える影響はなかなか小さくならない。かけて計算していては間に合わない。制約が小さいのは、このように意地悪なケースで指数的に回数が増えてしまい、精度を保つのが難しくなるからと思われる。DP遷移と高速化の方法ここで、期待値は一次式の形で表現できることを利用する。何回スタートに戻されたか、という点で分けて考察する。ごとに、以下の2つのDPを考える。あり、また、DPの遷移は以下のようになる。一次式の形で表せることがわかる。止まる」場合と遷移が微妙に異なる点に注意。これで、十分に期待値への影響が小さくなるまで計算を回すことが可能になった。それぞれDPで計算する。マス手前までの連続区間の和が必要になるので、最初から累積和で保持しておくとよい。yprint(ans)これは難しかった。末尾からの1次式DP1次式の係数をDPするのは同じだけど、繰り返し収束するまで計算しなくてもいいし、より正確な値が出る解法。先頭からではなく、末尾からおこなう。