Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 298 E問題 Unfair Sugoroku

AtCoder ABC ABC298 E問題 500 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$1$ から $N$ までの番号が振られたマスがあるすごろくを高橋君と青木君が行う.

高橋君はマス $A$ に, 青木君はマス $B$ におり, 高橋君から以下の行動を交互に行う.

高橋君: $P$ 面サイコロを振る. このサイコロは $1,2, \dots, P$ の目が同様に確からしく出る.
青木君: $Q$ 面サイコロを振る. このサイコロは $1,2, \dots, Q$ の目が同様に確からしく出る.

地点 $x$ にいる人がサイコロを振り $k$ の目が出た場合, マス $\min(x+k,N)$ に移動する.

先にマス $N$ に到達した人が勝ちであるとき, 高橋君が勝つ確率を求めよ.

制約

$2 \leq N \leq 100$
$1 \leq A,B \lt N$
$1 \leq P,Q \leq 10$

解法

動的計画法で求める. ${\rm DP}(X,i,j)$ を次のようにして定める.

高橋君がマス $i$ , 青木君がマス $j$ にいる状況で, 次に移動する人が $X$ ( $X=T$ : 高橋君, $X=A$ : 青木君) である場合において, 高橋君が勝つ確率.

ベースケースは $i=N$ または $j=N$ の場合で,

${\rm DP}(X,N,j)=1, \quad (X \in \{T,A\}, 1 \leq j \lt N)$

${\rm DP}(X,i,N)=1, \quad (X \in \{T,A\}, 1 \leq i \lt N)$

となる. なお, このゲームのルールから, $i=j=N$ となることはありえない.

高橋君のターンについて考える. $p=1,2, \dots, P$ の目が出る確率が $\dfrac{1}{P}$ で起こるので,

$\displaystyle {\rm DP}(T,i,j)=\dfrac{1}{P} \sum_{p=1}^P {\rm DP}(A,\min(i+p,N),j)$

となる.

青木君のターンについても同様に考えることで,

$\displaystyle {\rm DP}(A,i,j)=\dfrac{1}{Q} \sum_{q=1}^Q {\rm DP}(T,i,\min(j+q,N))$

となる.

これにより, 求めるべき解答は ${\rm DP}(T,A,B)$ である. これは $O(N^2(P+Q))$ 時間で求めることができる.