問題一覧 > 通常問題

No.1478 Simple Sugoroku

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-4}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 100
作問者 : nok0nok0 / テスター : 👑 fairy_lettucefairy_lettuce oteraotera ygussanyygussany PCTprobabilityPCTprobability
9 ProblemId : 5790 / 出題時の順位表
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。