結果

問題 No.463 魔法使いのすごろく🎲
ユーザー lam6er
提出日時 2025-03-20 20:26:52
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,190 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 77,188 KB
最終ジャッジ日時 2025-03-20 20:28:28
合計ジャッジ時間 7,227 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def compute_next_pos(i, k, n):
    current = i
    direction = 1
    steps_left = k
    while steps_left > 0:
        next_p = current + direction
        if next_p > n:
            direction = -1
            next_p = current + direction
        current = next_p
        steps_left -= 1
    return current

n, m = map(int, input().split())
c = list(map(int, input().split()))
c = [0] + [0] + c + [0]  # indexes from 0 to n+1, but ignore 0 and adjust for 1-based

# Initialize next_pos: next_pos[i][k] for 1 <= i <=n, 1 <=k <=m
next_pos = [[0] * (m+1) for _ in range(n+2)]  # [1..n][1..m]
for i in range(1, n+1):
    for k in range(1, m+1):
        next_pos[i][k] = compute_next_pos(i, k, n)

# DP tables: E0 is E[i][0], E1 is E[i][1]
E0 = [0.0] * (n + 2)
E1 = [0.0] * (n + 2)

iterations = 0
epsilon = 1e-14
max_diff = 1.0

# Iterate until convergence
while max_diff > epsilon:
    new_E0 = [0.0] * (n + 2)
    new_E1 = [0.0] * (n + 2)
    max_diff = 0.0

    for i in range(1, n + 1):
        if i == n:
            new_E0[i] = 0.0
            new_E1[i] = 0.0
            continue

        # Compute new_E0[i]: u=0
        c_i = c[i] if (2 <= i < n) else 0.0

        # Option 1: No magic
        sum_no_magic = 0.0
        for k in range(1, m+1):
            j = next_pos[i][k]
            sum_no_magic += E0[j]
        sum_no_magic /= m

        # Option 2: Use magic, choose best k
        sum_magic = float('inf')
        for k in range(1, m+1):
            j = next_pos[i][k]
            current_e = E1[j]
            if current_e < sum_magic:
                sum_magic = current_e

        new_E0_i = c_i + min(sum_no_magic, sum_magic)

        # Compute new_E1[i]: u=1
        sum_e1 = 0.0
        for k in range(1, m+1):
            j = next_pos[i][k]
            sum_e1 += E1[j]
        sum_e1 /= m
        new_E1_i = c_i + sum_e1

        new_E0[i] = new_E0_i
        new_E1[i] = new_E1_i

    # Update max_diff
    for i in range(1, n + 1):
        diff0 = abs(new_E0[i] - E0[i])
        diff1 = abs(new_E1[i] - E1[i])
        max_diff = max(max_diff, diff0, diff1)

    # Update E0 and E1
    E0, new_E0 = new_E0, E0
    E1, new_E1 = new_E1, E1

print("{0:.10f}".format(E0[1]))
0