Day 176-Q2 — 2026-10-12 | やり直しのある最速クリア（答え E が遷移の中に現れる期待値 DP を、方策反復＝Newton 法で解く）

📋 コピーimport sys


def main():
    data = sys.stdin.buffer.read().split()
    n, lim = int(data[0]), int(data[1])
    F = [int(x) for x in data[2:2 + 3 * n:3]]
    S = [int(x) for x in data[3:3 + 3 * n:3]]
    P = [int(x) / 100 for x in data[4:4 + 3 * n:3]]

    INF = float('inf')

    def evaluate(E):
        """E を「やり直したときの残り期待時間」と仮定して最適方策を選び、
        その方策での D(0,0) を a + b*E の形で返す（b = やり直しで始めに戻る確率）"""
        # nxt_a[t], nxt_b[t]: i+1 面クリア済み・経過 t のときの a, b（t > lim は強制やり直し = 0 + 1*E）
        nxt_a = [0.0] * (lim + 1)
        nxt_b = [0.0] * (lim + 1)
        for i in range(n - 1, -1, -1):
            f, s, p = F[i], S[i], P[i]
            q = 1.0 - p
            cur_a = [0.0] * (lim + 1)
            cur_b = [1.0] * (lim + 1)              # 既定はやり直し（a=0, b=1）
            tmax = lim if i > 0 else 0              # 0 面目は t=0 だけ
            for t in range(tmax + 1):
                tf, ts = t + f, t + s
                if tf > lim:
                    ca = p * f + q * s              # 速くても制限超え → 遊んだ後に必ずやり直し
                    cb = 1.0
                elif ts > lim:
                    ca = p * (f + nxt_a[tf]) + q * s
                    cb = p * nxt_b[tf] + q
                else:
                    ca = p * (f + nxt_a[tf]) + q * (s + nxt_a[ts])
                    cb = p * nxt_b[tf] + q * nxt_b[ts]
                if i == 0 or E == INF or ca + cb * E < E:   # 続けた方が得なら続ける
                    cur_a[t] = ca
                    cur_b[t] = cb
            nxt_a, nxt_b = cur_a, cur_b
        return nxt_a[0], nxt_b[0]

    E = INF
    for _ in range(100):                            # 方策反復（Newton 法）。実際は数回で止まる
        a, b = evaluate(E)
        newE = a / (1.0 - b)
        if newE >= E * (1 - 1e-15):
            break
        E = newE
    print(f"{E:.10f}")


main()