結果

問題 No.463 魔法使いのすごろく🎲
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:25:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 795 ms / 2,000 ms
コード長 2,537 bytes
記録
コンパイル時間 271 ms
コンパイル使用メモリ 82,044 KB
実行使用メモリ 77,120 KB
最終ジャッジ日時 2025-03-31 17:26:03
合計ジャッジ時間 7,694 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n, m = int(input[idx]), int(input[idx + 1])
    idx += 2
    c = list(map(int, input[idx:idx + n - 2]))
    idx += n - 2

    # c_val[i] is the loss at position i (1-based)
    c_val = [0] * (n + 1)  # positions 0 and n have 0 (0 is unused)
    for i in range(2, n):
        c_val[i] = c[i - 2]

    e0_prev = [0.0] * (n + 1)  # state (x, 0)
    e1_prev = [0.0] * (n + 1)  # state (x, 1)

    max_iterations = 100000
    tolerance = 1e-13

    for _ in range(max_iterations):
        e0_current = [0.0] * (n + 1)
        e1_current = [0.0] * (n + 1)

        # Update e1 (magic used)
        for x in range(1, n):
            total = 0.0
            for d in range(1, m + 1):
                new_pos = x + d
                if new_pos > n:
                    new_pos = 2 * n - new_pos
                if new_pos == n:
                    term = 0.0
                else:
                    term = c_val[new_pos] + e1_prev[new_pos]
                total += term
            e1_current[x] = total / m

        # Update e0 (magic not used yet)
        for x in range(1, n):
            # Option a: use magic, find best d
            min_a = float('inf')
            for d in range(1, m + 1):
                new_pos = x + d
                if new_pos > n:
                    new_pos = 2 * n - new_pos
                if new_pos == n:
                    term = 0.0
                else:
                    term = c_val[new_pos] + e1_prev[new_pos]
                if term < min_a:
                    min_a = term
            # Option b: do not use magic, average all d
            total_b = 0.0
            for d in range(1, m + 1):
                new_pos = x + d
                if new_pos > n:
                    new_pos = 2 * n - new_pos
                if new_pos == n:
                    term = 0.0
                else:
                    term = c_val[new_pos] + e0_prev[new_pos]
                total_b += term
            avg_b = total_b / m
            e0_current[x] = min(min_a, avg_b)

        # Check for convergence
        max_diff = 0.0
        for x in range(1, n):
            diff0 = abs(e0_current[x] - e0_prev[x])
            diff1 = abs(e1_current[x] - e1_prev[x])
            max_diff = max(max_diff, diff0, diff1)
        if max_diff < tolerance:
            break

        # Update previous values
        e0_prev, e1_prev = e0_current, e1_current

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

if __name__ == "__main__":
    main()
0