問題一覧 > 通常問題

No.1478 Simple Sugoroku

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が104 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 124
作問者 : nok0nok0 / テスター : fairy_lettucefairy_lettuce oteraotera 👑 ygussanyygussany PCTprobabilityPCTprobability
17 ProblemId : 5790 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-03-21 12:17:15

問題文

nok0くんはすごろくで遊んでいます。

このすごろくには直線状に並んだ N 個のマスが存在し、左から順に 1,2,,N と番号がついています。

すごろくのうち M 個のマス B1,B2,,BM はワープマスとなっています。

nok0くんは最初マス 1 に存在し、マス N に移動するまで毎回以下の 2 つの操作のいずれかを選択し実行します。

  • 操作 1 : 今nok0くんがいるマスをマス i とする。マス i+1 に移動する。
  • 操作 2 : この操作は今nok0くんがいるマスがワープマスの時のみ選択できる。ワープマス(nok0くんがいるマスも含む)を一様ランダムに一つ選び、そのワープマスに移動する。

nok0くんが操作回数の期待値を最小化するように行動するとき、操作回数の期待値を求めてください。

制約

  • 入力は全て整数である。
  • 1N109
  • 1Mmin(N,105)
  • 1B1<B2<<BMN

入力

N M
B1 B2  BM

出力

nok0くんが操作回数の期待値を最小化するように行動したとき、操作回数の期待値を出力せよ。正しい値との絶対誤差または相対誤差が 104 以下であれば正解とみなされる。

サンプル

サンプル1
入力
2 1
2
出力
1.0

操作 11 回行えばゴールに辿りつきます。

サンプル2
入力
100 2
1 100
出力
2.00

ゴールにたどり着くまで操作 2 を繰り返すのが最善です。操作回数の期待値は i=1(12)ii=2.0 です。

サンプル3
入力
10000 9
100 200 300 400 1900 1901 2900 2901 2904
出力
7200.3333333333

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。