結果

問題 No.463 魔法使いのすごろく🎲
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:57:58
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,719 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 81,804 KB
実行使用メモリ 76,136 KB
最終ジャッジ日時 2025-04-15 22:59:24
合計ジャッジ時間 2,910 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 WA * 8 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, m = map(int, input().split())
c = list(map(int, input().split()))
c_array = [0] * (n + 1)
for i in range(2, n):
    c_array[i] = c[i - 2]

def get_next(i, d):
    next_pos = i + d
    if next_pos <= n:
        return next_pos
    else:
        excess = next_pos - n
        return n - excess

INF = float('inf')
dp = [[INF] * 2 for _ in range(n + 1)]
dp[n][0] = 0.0
dp[n][1] = 0.0

for i in range(n-1, 0, -1):
    # Compute dp[i][1]
    a = 0.0
    b = 0
    for d in range(1, m+1):
        j = get_next(i, d)
        if j == n:
            cost = dp[j][1]
        else:
            cost = dp[j][1] + c_array[j]
        if j == i:
            a += c_array[j]
            b += 1
        else:
            a += cost
    denominator = m - b
    if denominator == 0:
        dp[i][1] = 0.0  # This case should not occur given problem constraints
    else:
        dp[i][1] = a / denominator

    # Compute dp[i][0]
    # E_no_magic calculation
    a_no = 0.0
    b_no = 0
    for d in range(1, m+1):
        j = get_next(i, d)
        if j == n:
            cost = dp[j][0]
        else:
            cost = dp[j][0] + c_array[j]
        if j == i:
            a_no += c_array[j]
            b_no += 1
        else:
            a_no += cost
    denominator_no = m - b_no
    if denominator_no == 0:
        e_no = 0.0
    else:
        e_no = a_no / denominator_no

    # E_magic calculation
    min_magic = INF
    for d in range(1, m+1):
        j = get_next(i, d)
        if j == n:
            cost = dp[j][1]
        else:
            cost = dp[j][1] + c_array[j]
        if cost < min_magic:
            min_magic = cost
    e_magic = min_magic

    dp[i][0] = min(e_no, e_magic)

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