ABC224-G Roll or Increment 雑解法

みんなはちゃんと証明しましょう

問題

リンクはこちら

解法

現在の出目が $i$ の時、出目を $T$ に変える最適な戦略でかかる合計コストを $C(i)$ と書くことにします。 戦略はゴールまで増やし続けるか一旦振り直すかです。

振り直した後にかかるコストの期待値を $r$ と置きます。すると、

$$ C(i) = \begin{cases} \min(A(T - i), B + r) & (i \le T) \\ B + r & (i > T) \end{cases} $$

です。さらに、$r = \sum C(i) / N$ です。

ここで、 $r$ をある値 $r_{a}$ だと仮定します。すると $C(i)$ が定まり、上の式を用いて $r$ が計算できます。これを $r_b$ とします。 $r_a$ が $r_b$ より大きいとき、真の $r$ は $r_a$ より小さく、 小さいときは $r_a$ より大きいはずです。 このように $r$ を二分探索することで真の $r$ および $C(i)$ が計算できます。求める答えは $C(S)$ です。

from math import ceil

N, S, T, A, B = map(float, input().split())

hi = N * max(A, B)
lo = 0
for _ in range(64):
    ra = (hi + lo) / 2.

    # A * (T - i) <= B + r である i の個数
    count = min(T, ceil((ra + B) / A))
    border = T - count

    # C(i) の総和
    total = (ra + B) * (border + (N - T)) + A * (count - 1) * count / 2
    rb = total / N

    if ra > rb:
        hi = ra
    else:
        lo = rb

r = (hi + lo) / 2
if S > T:
    ans = r + B
else:
    ans = min(A * (T - S), r + B)
print(f"{ans:.16f}")

提出コード

提出コード（Python）

雑すぎる