$W_i$ に関して、あなたは持ち点でディーラーを真に上回らないといけないので、
$P_i$ の累積和を取って1つ右にずらしたものが暫定の $W_i$ となる。
from itertools import accumulate
from operator import add
class SegmentTreeInjectable:
"""
単位元生成関数 identity_factory と二項演算関数 func を外部注入するセグメント木
[生成]
SegmentTreeInjectable(n, identity_factory, func)
SegmentTreeInjectable.from_array(array, identity_factory, func) # 既存の配列より作成
[関数]
add(i, x) Aiにxを加算
update(i, x) Aiをxに書き換え
get_range(a, b) [a, b) の集約値を得る
get_all() 全ての集約値を得る
get_point(i) Aiを得る
leftmost(a, b, x, ev) [a, b) の範囲で、ev(x, Ai)=True となる最も左の i を得る（前提条件あり）
rightmost(a, b, x, ev) [a, b) の範囲で、ev(x, Ai)=True となる最も右の i を得る（前提条件あり）
debug_print() 深さ毎に整形して出力する
"""
def __init__(self, n, identity_factory, func):
n2 = 1 << (n - 1).bit_length()
self.offset = n2
self.tree = [identity_factory() for _ in range(n2 << 1)]
self.func = func
self.idf = identity_factory
@classmethod
def from_array(cls, arr, identity_factory, func):
""" 既存の配列から生成 """
ins = cls(len(arr), identity_factory, func)
ins.tree[ins.offset:ins.offset + len(arr)] = arr
for i in range(ins.offset - 1, 0, -1):
l = i << 1
r = l + 1
ins.tree[i] = func(ins.tree[l], ins.tree[r])
return ins
def add(self, i, x):
"""
Aiにxを加算
:param i: index (0-indexed)
:param x: add value
"""
i += self.offset
self.tree[i] = self.func(self.tree[i], x)
self.__upstream(i)
def update(self, i, x):
"""
Aiの値をxに更新
:param i: index(0-indexed)
:param x: update value
"""
i += self.offset
self.tree[i] = x
self.__upstream(i)
def __upstream(self, i):
tree = self.tree
func = self.func
while i > 1:
i >>= 1
lch = i << 1
rch = lch | 1
tree[i] = func(tree[lch], tree[rch])
def get_range(self, a, b):
"""
[a, b)の値を得る
:param a: index(0-indexed)
:param b: index(0-indexed)
"""
tree = self.tree
func = self.func
result_l = self.idf()
result_r = self.idf()
l = a + self.offset
r = b + self.offset
while l < r:
if r & 1:
result_r = func(tree[r - 1], result_r)
if l & 1:
result_l = func(result_l, tree[l])
l += 1
l >>= 1
r >>= 1
return func(result_l, result_r)
def get_all(self):
return self.tree[1]
def get_point(self, i):
return self.tree[i + self.offset]
def leftmost(self, a, b, x, ev):
"""
[a, b) の範囲で、ev(x, 値) = True となる最初の index を得る。存在しない場合は-1。
使用できる条件:
[l, r) の集約値を y としたとき、ev(x, y)=True となることが、
l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
"""
tree = self.tree
l = a + self.offset
r = b + self.offset
r_found = -1
while l < r:
if l & 1:
if ev(x, tree[l]):
return self._leftmost_sub(l, x, ev)
l += 1
if r & 1:
if ev(x, tree[r - 1]):
r_found = r - 1
l >>= 1
r >>= 1
if r_found == -1:
return -1
return self._leftmost_sub(r_found, x, ev)
def _leftmost_sub(self, i, x, ev):
"""
tree-index i が示す範囲で、ev(x, Aj)=True となる最も左のarray-index j を得る
（tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
"""
tree = self.tree
while i < self.offset:
l = i << 1
if ev(x, tree[l]):
i = l
else:
i = l + 1
return i - self.offset
def rightmost(self, a, b, x, ev):
"""
[a, b) の範囲で、ev(x, 値) = True となる最後の index を得る。存在しない場合は-1。
使用できる条件:
[l, r) の集約値を y としたとき、ev(x, y)=True となることが、
l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
"""
tree = self.tree
l = a + self.offset
r = b + self.offset
l_found = -1
while l < r:
if r & 1:
if ev(x, tree[r - 1]):
return self._rightmost_sub(r - 1, x, ev)
if l & 1:
if ev(x, tree[l]):
l_found = l
l += 1
l >>= 1
r >>= 1
if l_found == -1:
return -1
return self._rightmost_sub(l_found, x, ev)
def _rightmost_sub(self, i, x, ev):
"""
tree-index i が示す範囲で、ev(x, Aj)=True となる最も右のarray-index j を得る
（tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
"""
tree = self.tree
while i < self.offset:
l = i << 1
if ev(x, tree[l + 1]):
i = l + 1
else:
i = l
return i - self.offset
def debug_print(self):
i = 1
while i <= self.offset:
print(self.tree[i:i * 2])
i <<= 1
n, l, d = map(int, input().split())
p = 1 / d
dp = [0] * (n + d + 5)
dp[0] = 1
dp[1] = -1
for i in range(n + 1):
dp[i + 1] += dp[i]
if i < l:
k = dp[i] * p
dp[i + 1] += k
dp[i + d + 1] -= k
dp[i] = 0
y_burst = 1 - sum(dp[:n + 1])
win = list(accumulate([y_burst] + dp))
win[n + 1:] = [0.] * len(win[n + 1:])
sgt = SegmentTreeInjectable.from_array(win, float, add)
for i in range(n, -1, -1):
no_dice = win[i]
go_dice = sgt.get_range(i + 1, i + d + 1) * p
if no_dice < go_dice:
sgt.update(i, go_dice)
# sgt.debug_print()
ans = sgt.get_point(0)
print(ans)