結果
問題 |
No.463 魔法使いのすごろく🎲
|
ユーザー |
![]() |
提出日時 | 2025-04-16 15:59:39 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,078 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 81,272 KB |
実行使用メモリ | 96,308 KB |
最終ジャッジ日時 | 2025-04-16 16:02:01 |
合計ジャッジ時間 | 11,065 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | AC * 21 TLE * 1 -- * 14 |
ソースコード
n, m = map(int, input().split()) c = list(map(int, input().split())) def get_cost(i): if 2 <= i <= n-1: return c[i-2] else: return 0 def next_pos(i, d): pos = i rem = d direction = 1 while rem > 0: next_p = pos + direction if next_p == n: direction = -1 elif next_p == 1: direction = 1 pos = next_p rem -= 1 return pos # Initialize DP arrays. dp[i][0] is state 0 (not used magic), dp[i][1] is state 1 (used magic) dp = [[0.0 for _ in range(2)] for __ in range(n+1)] # 1-based indexing eps = 1e-12 max_iterations = 1000000 iteration = 0 while True: new_dp = [[0.0 for _ in range(2)] for __ in range(n+1)] # Update state 1 (already used magic) for i in range(1, n+1): if i == n: new_dp[i][1] = 0.0 continue cost = get_cost(i) total = 0.0 for d in range(1, m+1): j = next_pos(i, d) total += dp[j][1] new_dp[i][1] = cost + total / m # Update state 0 (not used magic yet) for i in range(1, n+1): if i == n: new_dp[i][0] = 0.0 continue cost = get_cost(i) # Option 1: do not use magic here total = 0.0 for d in range(1, m+1): j = next_pos(i, d) total += dp[j][0] option1 = total / m # Option 2: use magic here, choose the best d min_val = float('inf') for d in range(1, m+1): j = next_pos(i, d) if dp[j][1] < min_val: min_val = dp[j][1] option2 = min_val new_dp[i][0] = cost + min(option1, option2) # Check convergence converged = True max_diff = 0.0 for i in range(1, n+1): for s in range(2): diff = abs(new_dp[i][s] - dp[i][s]) if diff > max_diff: max_diff = diff if max_diff < eps: break dp = new_dp iteration += 1 if iteration >= max_iterations: break print("{0:.10f}".format(dp[1][0]))