No.1478 Simple Sugoroku
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-4}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 124
作問者 :
nok0
/ テスター :
fairy_lettuce
otera
ygussany
PCTprobability
タグ : / 解いたユーザー数 124
作問者 :
nok0
/ テスター :
fairy_lettuce
otera
ygussany
PCTprobability
問題文最終更新日: 2021-03-21 12:17:15
問題文
nok0くんはすごろくで遊んでいます。
このすごろくには直線状に並んだ $N$ 個のマスが存在し、左から順に $1,2,\dots,N$ と番号がついています。
すごろくのうち $M$ 個のマス $B_1,B_2,\dots,B_M$ はワープマスとなっています。
nok0くんは最初マス $1$ に存在し、マス $N$ に移動するまで毎回以下の $2$ つの操作のいずれかを選択し実行します。
- 操作 $1$ : 今nok0くんがいるマスをマス $i$ とする。マス $i+1$ に移動する。
- 操作 $2$ : この操作は今nok0くんがいるマスがワープマスの時のみ選択できる。ワープマス(nok0くんがいるマスも含む)を一様ランダムに一つ選び、そのワープマスに移動する。
nok0くんが操作回数の期待値を最小化するように行動するとき、操作回数の期待値を求めてください。
制約
- 入力は全て整数である。
- $1\le N\le 10^9$
- $1\le M \le \mathrm{min}(N,10^5)$
- $ 1 \le B_1 < B_2 < \dots < B_M \le N$
入力
$N\ M$ $B_1\ B_2\ \dots\ B_M$
出力
nok0くんが操作回数の期待値を最小化するように行動したとき、操作回数の期待値を出力せよ。正しい値との絶対誤差または相対誤差が $10^{-4}$ 以下であれば正解とみなされる。
サンプル
サンプル1
入力
2 1 2
出力
1.0
操作 $1$ を $1$ 回行えばゴールに辿りつきます。
サンプル2
入力
100 2 1 100
出力
2.00
ゴールにたどり着くまで操作 $2$ を繰り返すのが最善です。操作回数の期待値は $\displaystyle\sum_{i=1}^{\infty} \left(\frac{1}{2}\right)^ii = 2.0$ です。
サンプル3
入力
10000 9 100 200 300 400 1900 1901 2900 2901 2904
出力
7200.3333333333
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。