ABC 275 E — Sugoroku 4

考察

N,M,K≤1000 だが M^K 個の出目列は列挙できない。一方、次の位置は現在位置と出目だけで決まり、勝利前の位置は 0,…,N-1 の有限状態である。M≤N なので j+d は高々 2N-1 で、N を越えた場合の到着位置は 2N-(j+d) と一度の反射で表せる。ゲームは N 到着時に終了するため、N の確率を次の回へ配らず、その時点で累積答えへ移すと『高々 K 回』を重複なく数えられる。確率は法 998244353 上で扱え、各等確率遷移はあらかじめ求めた M の逆元を掛ければよい。

採用する候補: 回数 i と勝利前の位置 j の確率 DP を行い、各出目へ 1/M ずつ遷移し、N に着いた確率を回数ごとに答えへ加える。

同じ回数・位置以後の確率過程を共有でき、終了後の不要な遷移も避けられる。

棄却する候補: 長さ 1,…,K のルーレット出目列を全列挙し、初めて N に着く列を数える。

候補数が M^K で、M≤10 でも K≤1000 には適用できない。

dp[0][0]=1 とし、i=0,…,K-1 で j<N と d=1,…,M を走査する。t=j+d が N 以下なら t、超えるなら 2N-t へ invM 倍を配り、t=N の分だけ答えに加える。

典型の発動条件

有限 Markov 過程の確率 DP

発動条件: 試行回数に上限があり、次状態が現在状態とランダムな結果だけで決まるとき。

回数×盤面位置に確率を集約し、等確率の出目へ分配する。

吸収時刻の累積

発動条件: 目標状態へ初めて到着した時点で過程が終了し、上限回数以内の成功確率を求めるとき。

目標への遷移確率を答えへ足し、目標状態からは遷移させない。

問題固有の要素

折り返し移動も M≤N により一度の反射式だけで閉じるので、特殊な盤面履歴を持たず位置 DP にできる。

別の問題へ持ち帰る視点: 反射・周期移動では、一手の最大幅から折返し回数を評価し、次状態の正規化式を先に作る。

正当性

非終端状態から全diceを1/Mで配り、超過は問題の反射式へ写すと一手の遷移確率を厳密に表す。到達時だけ答えへ加え終端からは再配布しないのでK手以内の初到達事象を重複なく合計する。

実装上の注意

  • M の逆元は一度だけ計算し、各遷移で冪乗を呼ばない。
  • N に着いた確率を dp の次 layerにも残す実装と累積加算を併用すると重複するため、どちらか一方の意味に統一する。

復習の核

  • N=2,M=2,K=1 の直接到着と、N=4で 3 から出目4が1へ反射する遷移を手計算し、吸収確率の扱いを確認する。

計算量と制約

時間

盤面終点N、dice M面、手数K。O(KNM)。

空間

rolling位置確率 O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: M \leq N \leq 1000; 1 \leq M \leq 10; 1 \leq K \leq 1000; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Sugoroku 4 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 確率過程・期待値DP

主題
  • 確率過程・期待値DP: 互いに排反な状態に確率を配り、遷移確率・吸収条件・総確率を保って分布や到達確率を計算できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 確率・期待値DP

    補助タグ: 法上の四則演算・高速累乗・逆元

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 確率過程・期待値DP

    • 互いに排反な状態に確率を配り、遷移確率・吸収条件・総確率を保って分布や到達確率を計算できる。

    先に読む単元:

    この解説で扱わないこと:

    • 二人零和ゲームの勝敗・Grundy数。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題