結果
問題 |
No.463 魔法使いのすごろく🎲
|
ユーザー |
![]() |
提出日時 | 2025-04-16 16:02:55 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,565 bytes |
コンパイル時間 | 366 ms |
コンパイル使用メモリ | 82,108 KB |
実行使用メモリ | 65,720 KB |
最終ジャッジ日時 | 2025-04-16 16:09:17 |
合計ジャッジ時間 | 2,753 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 35 RE * 1 |
ソースコード
n, m = map(int, input().split()) c = list(map(int, input().split())) cost = [0] * (n + 1) for i in range(2, n): cost[i] = c[i - 2] def next_pos(i, d): j = i + d if j > n: j = 2 * n - j return j INF = float('inf') dp = [[INF] * 2 for _ in range(n + 1)] dp[n][0] = 0.0 dp[n][1] = 0.0 EPS = 1e-12 MAX_ITER = 1000000 for _ in range(MAX_ITER): updated = False for i in range(n-1, 0, -1): for k in [1, 0]: if i == n: continue if dp[i][k] == INF: continue old_val = dp[i][k] new_val = 0.0 if k == 1: magic_min = INF for d in range(1, m + 1): j = next_pos(i, d) current_cost = cost[j] + dp[j][0] if current_cost < magic_min: magic_min = current_cost exp_no_magic = 0.0 for d in range(1, m + 1): j = next_pos(i, d) exp_no_magic += (cost[j] + dp[j][1]) exp_no_magic /= m new_val = min(magic_min, exp_no_magic) else: exp = 0.0 for d in range(1, m + 1): j = next_pos(i, d) exp += (cost[j] + dp[j][0]) exp /= m new_val = exp if abs(new_val - old_val) > EPS: updated = True dp[i][k] = new_val if not updated: break print("{0:.10f}".format(dp[1][1]))