Problem C : Minimal Backgammon †問題概要 †ものすごく単純化されたバックギャモン。 直線状に N+1 個のマスが並んでおり、サイコロの目に従ってマス 0 からマス N までコマを移動させるのがゲームの目的。ゴールにはぴったりたどり着く必要があり、行き過ぎが発生する場合は行き過ぎた分だけマスを戻る必要がある。 マス 1 からマス N-1 までの間には以下のような特殊なマスが存在することがある。
マスの構成が与えられたとき、ターン T までの間にゴールできる確率を求めよ。 (三廻部; Nov 11, 2007) 解法 †動的計画法。確率を変化させる動的計画法と、場合の数を変化させる動的計画法が考えられる。 以下に確率を変化させる例を示す。 表中の値は、そのターンにそのマスにコマが存在する確率を示す。 ターン 0:
↓ ターン 1:
あるマスにコマがいるとき、そこから 1 〜 6 個先のマスに進む確率はそれぞれ 1/6 である。そのような確率の変化を全て加算して、次のターンに各マスにコマが存在する確率を計算する。 一回休みの状態を表すために B のマスには休み状態を表す確率の保存が別途必要になる。 T が大きいときには誤差の降り積もりを意識する必要があるかも。 議論・その他 †ファイルを添付する † mikurube_C.cpp 1524件
[詳細]
|
