その場合は-1を出力する。a))先頭からだと、ルーレット1回分の加算値が確率になるので、期待値と確率を両方持たないといけないけど、末尾からだと1でよいので、こっちの方が計算楽だった。2通りの方法で表せるんじゃ無いの、と思うんだけど、なんか答えが合わなくなる。後ろからだとできるのに、違いは何なんだろうか。1次式で行う必要は無く、「1周目で」到達する場合の回数期待値と確率を直接求めればよい。得る試行を、はじめて成功させるまでに得るスコア期待値」を算出できる。DPの遷移は以下のようになる。$g(j)=\dfrac{DP_P[j]}{M}$スタートに戻るマスはともに0最終マスのみ遷移が変わるのでそこに留意して、以下が求められる。\sum_{t=0}^{\infty}p(1-p)^t(X+tY)=\frac{pX+(1-p)Y}{p}=\frac{x+y}{p}$という、単純な数式となる。Wikipediaこれを計算してやれば、答えとなる。飛ぶ」などだったら、やはり末尾からDPの方が汎用性はあるか。仮定することでも、求めることができる。最初の見積もりが大きすぎたので、次は小さい数で試す。なり、一次式DPなどと比較するとlogが付く分だけ若干重い。符号は変わらないことがいえる。符号は一致することがわかる。大小関係で次の範囲を決めるので、もし、中盤で偶然、演算誤差により次の探索範囲を誤ってしまえば、答えが離れたものとなってしまう。誤差のなるべく出ない方法で評価をする必要がある。なるため誤差が大きくなり、いくつかのテストケースでWAとなった。なるので大丈夫だった。二分探索なら、1次式DPでは解けないような問題でも解くことができる。「スタートに戻るマスを踏むと5回休みとなるが、いつでも自主的にスタートに戻ることもできて、その場合はペナルティなしで再スタートできる」みたいなルールとする。どちらが得?」みたいな比較ができない。二分探索なら、具体的な数値が入っているので比較でき、最適な戦略をとった場合の期待値を求めることができる。ikatakosメディアマネージャー文書の先頭へ。