C - すごろく
Editorial
/
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
黒猫のスヌケ君はすごろくで遊んでいます。
このすごろくでは変わったサイコロを使っています。 このサイコロには全部で N 個の面があり、それぞれの面が出る確率は全て同じです。 i 番目の面には整数 A_i が書かれていて、この面が出たときは駒をちょうど A_i マス進めます。
一方、このすごろくで使っているマスはそれほど変わったものではありません。 全部で M 個のマスが一列に並んでいて、1 番目のマスがスタート、M 番目のマスがゴールです。 i 番目のマスには整数 B_i が書かれていて、このマスに止まった場合は B_i の値によって以下のような効果を受けます。
- B_i が 0 以上である場合:駒をちょうど B_i マス進める。ただし、進めた先のマスの効果は受けない。
- B_i が 0 未満である場合:-B_i ターン休みとなる。
さて、スヌケ君がこのすごろくでゴールするまでにかかるターン数の期待値はいくらでしょうか?
なお、このすごろくではゴールを越えて進もうとした場合もゴールとみなされます。
制約
- 1≦N≦10^5
- 2≦M≦10^5
- 1≦A_i≦M
- -10≦B_i≦M
- B_1=B_M=0
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 ... A_N B_1 B_2 ... B_M
出力
ゴールするまでにかかるターン数の期待値を出力せよ。 ただし、絶対誤差または相対誤差が 10^{-4} 以下ならば正解とみなされる。
入力例 1
3 4 1 2 3 0 1 -1 0
出力例 1
2.00000000000000000000
最初のターンで出た目ごとに考えると以下のとおりである。
- 出た目が 1 の場合:1 マス進み、2 番目のマスに止まる。このマスの効果により、3 番目のマスまで進む。次のターンでは何が出てもゴールできるため、ゴールには合計 2 ターンかかる。
- 出た目が 2 の場合:2 マス進み、3 番目のマスに止まる。このマスの効果により、1 ターン休みとなる。次のターンは休みとなり、その次のターンでは何が出てもゴールできるため、ゴールには合計 3 ターンかかる。
- 出た目が 3 の場合:3 マス進み、4 番目のマスに止まる。すなわち、1 ターンでゴールできる。
したがって、期待値は 2/3 + 3/3 + 1/3 = 2 となる。
入力例 2
1 10 1 0 0 0 0 0 0 0 0 0 0
出力例 2
9.00000000000000177636
入力例 3
5 6 1 1 2 3 5 0 0 6 -10 1 0
出力例 3
4.47999999999999953815