結果

問題 No.463 魔法使いのすごろく🎲
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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]))
0