ABC298 E問題 Unfair Sugoroku

atcoder.jp

動的計画法で、サイコロを 回振ったあとに地点 にいる確率を とします。
さらに1回サイコロを振ることによって地点 のいずれかに確率で到達します。(地点が N より大きくなる時は、N に置き換えます。)
このことから、


…

と確率の加算を行います。これをループ処理することで、 回後にゴールに到達している確率が求められます。

高橋君と青木君について、この確率を求めます。
この確率は累積確率なので、その差分が高橋君が 回目に初めてゴールに到達する確率になります。
このとき、青木君がゴールに到達していない確率は 1 から累積確率を引いた値で、これらの確率の積で高橋君が回目にゴールに到達したときに高橋君が勝つ確率が求められます。
これを についてループすることで高橋君が勝つ確率が求められます。

コード例 (Julia)

_MOD = 998244353

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N, A, B, P, Q = readInts()

  p = invmod(P,_MOD)  # 1/P
  q = invmod(Q,_MOD)  # 1/Q

  taka = zeros(Int,N+1,N)
  aoki = zeros(Int,N+1,N)

  taka[1, A] = 1
  aoki[1, B] = 1

  # 高橋君の DP
  for i = 2:N
    for j = 1:N
      if taka[i-1, j] == 0
        continue
      end
      for k = 1 : P
        n = min(j+k, N)
        taka[i, n] += taka[i-1, j] * p
        taka[i, n] %= _MOD
      end
    end
  end

  # 青木君の DP
  for i = 2:N
    for j = 1:N
      if aoki[i-1, j] == 0
        continue
      end
      for k = 1 : Q
        n = min(j+k, N)
        aoki[i, n] += aoki[i-1, j] * q
        aoki[i, n] %= _MOD
      end
    end
  end

  ans = 0

  for i = 2:N
    prob = taka[i, N] - taka[i-1, N]  # 高橋君が i 回目にゴールに着く確率
    pa = 1 - aoki[i-1, N]             # 青木君がゴールに着いていない確率
    ans += (prob * pa) % _MOD
    ans %= _MOD
  end

  if ans < 0
    ans += _MOD
  end

  println(ans)

end  # function solve

# main
solve()