2007/Contest/東京大会

Problem C : Minimal Backgammon

問題概要

ものすごく単純化されたバックギャモン。

直線状に N+1 個のマスが並んでおり、サイコロの目に従ってマス 0 からマス N までコマを移動させるのがゲームの目的。ゴールにはぴったりたどり着く必要があり、行き過ぎが発生する場合は行き過ぎた分だけマスを戻る必要がある。

マス 1 からマス N-1 までの間には以下のような特殊なマスが存在することがある。

  • Lose one turn (L) : 一回休み
  • Go back to the start (B) : 振り出しに戻る

マスの構成が与えられたとき、ターン T までの間にゴールできる確率を求めよ。 (三廻部; Nov 11, 2007)

解法

動的計画法。確率を変化させる動的計画法と、場合の数を変化させる動的計画法が考えられる。

以下に確率を変化させる例を示す。 表中の値は、そのターンにそのマスにコマが存在する確率を示す。

ターン 0:

マス0マス1マス2マス3マス4マス5マス6
LB
通常1.0000.0000.0000.0000.0000.0000.000
休み0.0000.0000.0000.0000.0000.0000.000

ターン 1:

マス0マス1マス2マス3マス4マス5マス6
LB
通常0.1670.1670.0000.1670.1670.0000.167
休み0.0000.0000.1670.0000.0000.0000.000

あるマスにコマがいるとき、そこから 1 〜 6 個先のマスに進む確率はそれぞれ 1/6 である。そのような確率の変化を全て加算して、次のターンに各マスにコマが存在する確率を計算する。

一回休みの状態を表すために B のマスには休み状態を表す確率の保存が別途必要になる。

T が大きいときには誤差の降り積もりを意識する必要があるかも。
確率ではなく場合の数を保存することで誤差の降り積もりを回避できる。 (三廻部; Nov 11, 2007)

議論・その他


ファイルを添付する

filemikurube_C.cpp 1478件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: filemikurube_C.cpp 1478件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:39 (5277d)