結果

問題 No.463 魔法使いのすごろく🎲
ユーザー lam6er
提出日時 2025-04-15 23:01:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,240 ms / 2,000 ms
コード長 2,170 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 76,588 KB
最終ジャッジ日時 2025-04-15 23:02:33
合計ジャッジ時間 7,936 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    m = int(input[idx])
    idx += 1
    c = list(map(int, input[idx:idx + (n-2)])) if n > 2 else []
    idx += (n-2)
    
    def get_j(i, k):
        total = i + k
        if total <= n:
            return total
        else:
            t = total - n
            cycle = 2 * (n - 1)
            if cycle == 0:
                return n
            r = t % cycle
            if r == 0:
                return n
            elif r <= n - 1:
                return n - r
            else:
                return r - (n - 1) + 1
    
    epsilon = 1e-12
    max_iter = 1000000
    
    # Initialize DP tables
    prev_dpA = [0.0] * (n + 1)
    prev_dpB = [0.0] * (n + 1)
    
    for _ in range(max_iter):
        new_dpA = [0.0] * (n + 1)
        new_dpB = [0.0] * (n + 1)
        
        for i in range(1, n):
            # Compute dpB[i]
            sum_b = 0.0
            for k in range(1, m + 1):
                j = get_j(i, k)
                cost_j = c[j - 2] if 2 <= j <= n - 1 else 0.0
                sum_b += cost_j + prev_dpB[j]
            new_dpB[i] = sum_b / m
            
            # Compute dpA[i]
            sum_a = 0.0
            min_magic = float('inf')
            for k in range(1, m + 1):
                j = get_j(i, k)
                cost_j = c[j - 2] if 2 <= j <= n - 1 else 0.0
                sum_a += cost_j + prev_dpA[j]
                current = cost_j + prev_dpB[j]
                if current < min_magic:
                    min_magic = current
            e_normal = sum_a / m
            e_magic = min_magic
            new_dpA[i] = min(e_normal, e_magic)
        
        new_dpA[n] = 0.0
        new_dpB[n] = 0.0
        
        max_diff = 0.0
        for i in range(1, n + 1):
            max_diff = max(max_diff, abs(new_dpA[i] - prev_dpA[i]))
            max_diff = max(max_diff, abs(new_dpB[i] - prev_dpB[i]))
        
        if max_diff < epsilon:
            break
        
        prev_dpA, prev_dpB = new_dpA, new_dpB
    
    print("{0:.10f}".format(prev_dpA[1]))

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