风险情景树的最差叶 PnL
Worst-Case Leaf PnL on a Risk-Officer Scenario Tree
开始编码你拿到一个嵌套 dict,描述未来 PnL 离散化分支结构。内部节点带 prob 与 children 列表;终端节点带 prob 与一个有限 pnl。根本身就是终端——{"prob": 1.0, "pnl": <finite-float>}——是"完全不分支"的退化情形。请把结构走一遍,以单个 float 返回根可达的所有终端中 pnl 最差(即最小)的那个值,无关具体路径:
请用单次递归 DFS 在 O(N) 时间内实现 solution(tree) -> float。prob 是诱饵字段:它按惯例出现在输入里,但本题不许读它。按 child.prob 加权得到的是期望——那是另一道题。所有 pnl 都为正时返回最小的正数——"最差"严格等于 min,不是"有负取最负、否则取零"。内部节点 children 为空列表时,其贡献为 +inf(被 running min 自动跳过)——永远不会成为最差。根本身就是终端的合法退化输入直接返回它的 pnl。
例
solution({
"prob": 1.0,
"children": [
{"prob": 0.7, "pnl": 250.0},
{"prob": 0.2, "children": [
{"prob": 0.5, "pnl": 10.0},
{"prob": 0.5, "pnl": -800.0}
]},
{"prob": 0.1, "pnl": -75.0}
]
})返回 -800.0。根可达的四个终端 +250 / +10 / -800 / -75,最差是 -800。注意它藏在深度 2 上——只扫一层会漏掉。概率(顶层 0.7 / 0.2 / 0.1,内部 0.5 / 0.5)压根不读取;翻转它们也不影响答案。期望递推会给出完全不同的数。
实践背景
在离散化前向分布上做"地板损失"上报,是资本委员会做尾部诊断时最常见的动作。期望递推回答"桌上预期能赚多少",本题回答"结构允许多坏的情况发生"——最负的可达终端,无论选中它的路径概率多么微小。它支撑保证金摆位、Tier-1 缓冲归因、压力报表里最坏情形那一栏。在操作上区别于按概率加权的版本(那个版本会完整用到 prob),也区别于价格树后向归纳(那种递推是 max(continuation, exercise)):这里数学塌缩成可达终端上一个 min,而难点在于意识到 prob 是诱饵字段。
约束条件
- 入参 `tree` 是嵌套 `dict`。内部节点带 `prob`(float)和 `children`(节点列表——**允许为空**)。终端节点带 `prob`(float)和 `pnl`(有限 float)。根也可以直接就是终端(`{"prob": 1.0, "pnl": <finite>}`)——这是合法的退化输入。**保证**输入至少存在一个可达终端(因此答案是有限 float)。
- 内部节点的 `children` 为**空列表**时,其贡献为 `+inf`(在 running min 中被跳过)——永远不会成为最差。每个节点上的 `prob` 字段都被 `solution` 忽略;它是诱饵数据,兄弟之间的求和甚至可以不为 1.0。
- 每个 `pnl` 都是有限 float;深度最多 50,节点总数最多约 1500。输出是 `solution(tree)` 返回的单个 Python `float`——根可达终端中最小的 `pnl`(在上面的输入保证下,输出是有限 float)。
- 实现:`O(N)` 时间(节点总数),单次递归 DFS 在终端上跑 running min。不要枚举路径,不要做任何概率运算。
- 比较器:浮点 rel_tol `1e-12`、abs_tol `1e-12`。输出与某个输入 `pnl` 字节相等(`min` 只是比较),传播精确。
样例
Case 1 · degenerate root-as-leaf
输入: [{"prob":1,"pnl":12500}]
期望: 12500
退化输入:根本身就是叶子,直接返回根的 pnl 12500。
Case 2 · trivial single-leaf under root (one outcome)
输入: [{"prob":1,"children":[{"prob":1,"pnl":-42.5}]}]
期望: -42.5
根只挂一个叶子,最差就是 -42.5。
Case 3 · two-branch root: positive vs negative
输入: [{"prob":1,"children":[{"prob":0.6,"pnl":100},{"prob":0.4,"pnl":-50}]}]
期望: -50
两个叶子,最差是 -50;概率(0.6/0.4)被忽略。
Case 4 · three-branch flat root: rates up/flat/down
输入: [{"prob":1,"children":[{"prob":0.2,"pnl":250000},{"prob":0.6,"pnl":0},{"prob":0.2,"pnl":-300000}]}]
期望: -300000
三个叶子,最差 -300000;不管概率怎么挂权。
Case 5 · positive-only pnls — return min positive
输入: [{"prob":1,"children":[{"prob":0.25,"pnl":100},{"prob":0.25,"pnl":200},{"prob":0.25,"pnl":50},{"prob":0.25,"pnl":400}]}]
期望: 50
全正叶子,按定义返回最小正值 50。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · degenerate root-as-leaf
输入: [{"prob":1,"pnl":12500}]
期望: 12500
退化输入:根本身就是叶子,直接返回根的 pnl 12500。
Case 2 · trivial single-leaf under root (one outcome)
输入: [{"prob":1,"children":[{"prob":1,"pnl":-42.5}]}]
期望: -42.5
根只挂一个叶子,最差就是 -42.5。
Case 3 · two-branch root: positive vs negative
输入: [{"prob":1,"children":[{"prob":0.6,"pnl":100},{"prob":0.4,"pnl":-50}]}]
期望: -50
两个叶子,最差是 -50;概率(0.6/0.4)被忽略。
Case 4 · three-branch flat root: rates up/flat/down
输入: [{"prob":1,"children":[{"prob":0.2,"pnl":250000},{"prob":0.6,"pnl":0},{"prob":0.2,"pnl":-300000}]}]
期望: -300000
三个叶子,最差 -300000;不管概率怎么挂权。
Case 5 · positive-only pnls — return min positive
输入: [{"prob":1,"children":[{"prob":0.25,"pnl":100},{"prob":0.25,"pnl":200},{"prob":0.25,"pnl":50},{"prob":0.25,"pnl":400}]}]
期望: 50
全正叶子,按定义返回最小正值 50。