かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

yukicoder No.1478 Simple Sugoroku

yukicoder 動的計画法 典型 期待値 競技プログラミング 解説

問題はこちら

問題概要

{N}マスのマス目がある．以下の操作のうち{1}つを選び，マス{1}からマス{N}まで移動するときの操作回数の最小値を求めよ．

  • 操作{1}：マス{i}にいるときマス{N}に移動する．
  • 操作{2}：ワープマスにいるときランダムにワープマスに移動する．

ワープマスは{M}マスある({B_1,B_2,\cdots,B_M}がワープマス)．

{1\leq N \leq 10^9\\ 1\leq M\leq \min{(N,10^5)}}

解説


ワープマス以外のマスは操作が決まっているので圧縮します．

{N=6, M=3}のケース赤丸がワープマス．矢印が操作回数．
最左のワープマスより左のマスと最右のワープマスより右のマスの操作回数はあとでまとめて足します．
f:id:kanpurin:20210416224351p:plain

{dp[i]}を「マス{B_i}からマス{B_M}に移動するまでの最小の操作回数の期待値」とすると遷移の式は以下の様になります．

  • {dp[M]=0}
  • {\displaystyle dp[i]=\min{(dp[i+1]+B_{i+1}-B_{i},\frac{\sum_{k=1}^{M}dp[k]}{M}+1)}}

このままでは遷移がループしてるので，ある{X}を決めて

  • {dp[M]=0}
  • {\displaystyle dp[i]=\min{(dp[i+1]+B_{i+1}-B_{i},X+1)}}

を計算したときの{\displaystyle\frac{\sum_{k=1}^{M}dp[k]}{M}} (上の式により計算された値)が{X}より大きいなら真の{\displaystyle\frac{\sum_{k=1}^{M}dp[k]}{M}}の値は{X}より大きくなります．小さい場合も同様なので二分探索すればいいです．

二分探索の回数は適当に見積もって{\displaystyle 10^9×\frac{1}{2^n}\leq 10^{-4}}を満たせばいいので{50}回くらいすればいいです．

提出プログラム

https://yukicoder.me/submissions/648918

感想

この問題はすぐ解けたけど期待値問題苦手なので解説書きました．