結果
問題 |
No.463 魔法使いのすごろく🎲
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:01:18 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,719 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 81,668 KB |
実行使用メモリ | 76,036 KB |
最終ジャッジ日時 | 2025-04-15 23:02:06 |
合計ジャッジ時間 | 2,855 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 WA * 8 RE * 1 |
ソースコード
n, m = map(int, input().split()) c = list(map(int, input().split())) c_array = [0] * (n + 1) for i in range(2, n): c_array[i] = c[i - 2] def get_next(i, d): next_pos = i + d if next_pos <= n: return next_pos else: excess = next_pos - n return n - excess INF = float('inf') dp = [[INF] * 2 for _ in range(n + 1)] dp[n][0] = 0.0 dp[n][1] = 0.0 for i in range(n-1, 0, -1): # Compute dp[i][1] a = 0.0 b = 0 for d in range(1, m+1): j = get_next(i, d) if j == n: cost = dp[j][1] else: cost = dp[j][1] + c_array[j] if j == i: a += c_array[j] b += 1 else: a += cost denominator = m - b if denominator == 0: dp[i][1] = 0.0 # This case should not occur given problem constraints else: dp[i][1] = a / denominator # Compute dp[i][0] # E_no_magic calculation a_no = 0.0 b_no = 0 for d in range(1, m+1): j = get_next(i, d) if j == n: cost = dp[j][0] else: cost = dp[j][0] + c_array[j] if j == i: a_no += c_array[j] b_no += 1 else: a_no += cost denominator_no = m - b_no if denominator_no == 0: e_no = 0.0 else: e_no = a_no / denominator_no # E_magic calculation min_magic = INF for d in range(1, m+1): j = get_next(i, d) if j == n: cost = dp[j][1] else: cost = dp[j][1] + c_array[j] if cost < min_magic: min_magic = cost e_magic = min_magic dp[i][0] = min(e_no, e_magic) print("{0:.10f}".format(dp[1][0]))