所持金期待値 C#編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
ポスト
下記の問題をプログラミングしてみよう！
N 頂点 M 辺の DAG (非巡回有向グラフ) が与えられます。
i 番目の辺は頂点 U_i から頂点 V_i へ向かう有向辺です。
各頂点はすごろくのマスになっており、頂点 1 がスタートマス、頂点 N がゴールマスです。
その他の頂点はすべて所持金イベントマスです。
移動イベントマスには正整数が設定されており、いまいる頂点から距離がその正整数分だけ離れた頂点に移動することができます。
ただし、頂点 i から頂点 j への距離が L であるとは、頂点 i から頂点 j へ向かう長さ L のパスが存在することを指します (最短パスである必要はありません)。
さらに、頂点 1 からどの頂点へも到達可能であり、どの頂点からも頂点 N へ到達可能であることが保証されます。
このグラフ上のある頂点 i から j マス進むとき、頂点 i から距離が j である好きなマスに移動することができます。
また、頂点 i からゴールマスへの距離が j 以下であるなら、ゴールマスに移動することもできます。
あなたはいまスタートマスである頂点 1 にいます。
これからサイコロを振ってすごろくをします。サイコロの目は 1 から 6 の数字が等確率で出ます。
ゴール時の所持金が最大になるように行動したとき、ゴール時の所持金の期待値を求めてください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N M
B_1 C_1
B_2 C_2
...
B_N C_N
U_1 V_1
U_2 V_2
...
U_M V_M
・1 行目には 2 つの整数 N, M が与えられます。
・続く N 行の i 行目には、頂点 i の i マス目の種類 B_i と数字 C_i が与えられます。
・続く M 行の i 行目には、U_i から頂点 V_i へ向かう有向辺を表す整数が空白区切りで与えられます。
・入力は N+M+1 行となり、末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
ゴールしたときの所持金の期待値を 1 行に出力してください。
なお、想定解答との絶対誤差または相対誤差が 10^−6 以下であれば正解として扱われます。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・2 ≦ N ≦ 100
・1 ≦ M ≦ min(5000, N*(N-1)/2)
・B_i = "P" (所持金イベントマス)、-100 ≦ C_i ≦ 100 (2 ≦ i ≦ N-1)
・B_1 = "S" (スタートマス), C_1 = 0
・B_N = "G" (ゴールマス), C_N = 0
・1 ≦ U_i, V_i ≦ N
・U_i ≠ V_i
・(U_i, V_i) ≠ (U_j, V_j) (i ≠ j)
・グラフは DAG であり、頂点 1 からどの頂点へも到達可能であり、どの頂点からも頂点 N へ到達可能である
- 入力例1
-
5 8
S 0
P -71
P -37
P 95
G 0
1 4
1 2
1 5
3 2
3 5
4 2
2 5
1 3
- 出力例1
-
13.8611111111
- 入力例2
-
10 12
S 0
P 42
P -42
P 63
P -99
P -48
P -20
P 45
P 100
G 0
1 8
5 6
3 9
9 4
8 10
4 10
6 8
1 7
2 10
7 3
1 5
7 2
- 出力例2
-
43.4166666667
- 入力例3
-
15 18
S 0
P -33
P 83
P 33
P 63
P -31
P 46
P -77
P -12
P 15
P -77
P 80
P 48
P -95
G 0
1 2
10 15
1 4
1 3
6 9
13 12
3 15
8 15
6 11
12 15
11 13
5 14
7 5
9 8
4 10
1 6
2 7
14 10
- 出力例3
-
46.7939814815
