結果

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

ソースコード

diff # 

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