結果

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

ソースコード

diff # 

n, m = map(int, input().split())
c = list(map(int, input().split()))

def move(i, k, n):
    total = i + k
    if total <= n:
        return total
    over = total - n
    cycle = 2 * (n - 1)
    over %= cycle
    if over == 0:
        return n
    if over <= (n - 1):
        return n - over
    else:
        return over - (n - 1) + 1

eps = 1e-12
max_iter = 1000000

DPA = [0.0] * (n + 1)
DPB = [0.0] * (n + 1)

for _ in range(max_iter):
    next_DPA = DPA.copy()
    next_DPB = DPB.copy()
    converged = True
    for i in range(n, 0, -1):
        if i == n:
            next_DPA[i] = 0.0
            next_DPB[i] = 0.0
            continue
        
        # Calculate DPB[i]
        sum_b = 0.0
        for k in range(1, m + 1):
            j = move(i, k, n)
            if 2 <= j <= n - 1:
                cost = c[j - 2]
            else:
                cost = 0
            sum_b += cost + DPB[j]
        new_dpb = sum_b / m
        if abs(new_dpb - next_DPB[i]) > eps:
            converged = False
        next_DPB[i] = new_dpb
        
        # Calculate DPA[i]
        sum_a = 0.0
        for k in range(1, m + 1):
            j = move(i, k, n)
            if 2 <= j <= n - 1:
                cost = c[j - 2]
            else:
                cost = 0
            sum_a += cost + DPA[j]
        val_normal = sum_a / m
        
        val_magic = float('inf')
        for k in range(1, m + 1):
            j = move(i, k, n)
            if 2 <= j <= n - 1:
                cost = c[j - 2]
            else:
                cost = 0
            current = cost + DPB[j]
            if current < val_magic:
                val_magic = current
        new_dpa = min(val_normal, val_magic)
        if abs(new_dpa - next_DPA[i]) > eps:
            converged = False
        next_DPA[i] = new_dpa
    
    DPA, next_DPA = next_DPA, DPA
    DPB, next_DPB = next_DPB, DPB
    
    if converged:
        break

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