所有连续价位带扫荡的瓶颈深度合计:深度均匀度评分
Aggregate Bottleneck Bid-Depth across All Contiguous Price-Band Sweeps (Depth-Uniformity Score)
开始编码实现 solution(bid_depths: list[int]) -> int。输入 bid_depths 是 bid 侧 order book 的逐档 snapshot(长度 N),其中 bid_depths[i] 为第 i 档最优买价的 resting notional(正整数)。对每个连续价位带 [l..r](0 <= l <= r < N),整段一起扫荡时的瓶颈可部署深度即 bid_depths[l..r] 的最小值——段内最薄那一档限定了整段以挂单价能成交的 notional。snapshot 的深度均匀度合计评分就是所有连续价位带的瓶颈深度之和:
DUS = sum over all (l, r) with 0 <= l <= r < N of min(bid_depths[l], bid_depths[l+1], ..., bid_depths[r])
共有 N*(N+1)/2 个连续价位带。返回 DUS 对 1_000_000_007 取模的结果(K 档全等于 v 的均匀书评分为 K * v * (K + 1) / 2;总 notional 相同但带有一两个"软点"的书评分会远低于它的均值深度,因为每个跨过软点的价位带都把那一档的薄深度继承为自己的瓶颈)。
例:solution([4, 2, 5, 2, 3]) 返回 36。共 15 个子区间,其瓶颈 depth 依次为 4, 2, 2, 2, 2, 2, 2, 2, 2, 5, 2, 2, 2, 2, 3,求和得 36。两个最薄档(depth=2)在 15 个子区间里担任 min 的有 12 个(凡是覆盖到任何一个 depth=2 档的子区间均如此);最深档 5 仅在自身单点子区间贡献。该规模下取模并未生效,但在隐藏 N=3000 全 1e6 的压力测试中原始和约 4.5e12,已数倍于模数,必须正确取模。
需要明确的细节:空输入 N=0 返回 0;只有一档时返回 bid_depths[0](必然小于模数);K 档全等于 v 的均匀书返回 K * v * (K + 1) // 2 mod 1_000_000_007,因为每个子区间最小值都是 v 而子区间共 K*(K+1)/2 个;输入若违反 depth 范围,行为未定义,调用方负责校验;比对器是取模后的整数精确等于(无浮点容差)。
朴素 O(N^2) 双重循环在每对 (l, r) 上更新 running min,对可见小例可行,但在 N=5000 时内层迭代约 1.25e7 次,且必须小心放置取模位置;它在受 timing 闸门的隐藏 large 用例上会失败。标准解法是把问题翻转的单调栈:对每个下标 i 直接数清楚有多少个 (l, r) 把 bid_depths[i] 选为最小值,再乘以 bid_depths[i] 累加。严格/非严格不对称的 tie-break(左严格小于、右小于等于)即便在 uniform book 下也保证每个子区间恰好对应一个"代表"下标 i。函数骨架见 stubs/stub.py。
实践背景
研究侧从撮合系统拿到 bid 侧的逐档 snapshot,其中 bid_depths[i] 表示第 i 档最优买价的 resting notional,常想要一个单一数字概括"如果要连续扫荡一段任意价位带,这个 book 的可部署性如何"。某段连续扫 [l..r] 的瓶颈深度,等于段内最薄那一档的 resting depth——它限定了整段以挂单价能成交的 notional。把所有连续价带 [l..r] 的瓶颈累加,就得到该 snapshot 的 depth-uniformity 分数:均匀厚的 book 这个分数远大于"总 notional 相同但有几档软点卡住扫荡"的 book,即便它们在一阶矩(均值深度、总深度)上完全相同。该复合特征用于交易前的流动性打分,也是合成 order-book 生成器的快速 sanity 过滤。朴素地按 (l, r) 双重枚举为 O(N^2),N 超过几千档后就会拖累 snapshot 消费侧;工程目标是单档均摊 O(1),因此采用单调栈。不对称 tie-break 不是装饰:当书内存在多档 depth 完全相等时,仍要让每个子区间恰好被一个"代表"下标统计,否则 depth-uniformity 分数会被重复 depth 虚增,下游过滤器会因虚假厚度误触。模数采用标准素数 10**9 + 7,仅在最末一步取模,中间累加用 Python 任意精度 int 不丢精度。
约束条件
- 0 <= N <= 5000,其中 N 为 solution(bid_depths) 的输入长度
- 1 <= bid_depths[i] <= 1_000_000,单价位 resting-bid notional 可装入 32 位整数
- 输出为单个 int:所有 (l, r) 满足 0 <= l <= r < N 的 min(bid_depths[l..r]) 之和,对 1_000_000_007 取模
- 空输入 N=0 返回 0;输入若违反 depth 范围,行为未定义,调用方负责校验
- 输出按整数精确比对(取模后),不使用浮点容差
样例
Case 1 · statement-example: bid_depths [4, 2, 5, 2, 3] (depth-flavoured)
输入: [[4,2,5,2,3]]
期望: 36
15 个子区间的瓶颈 depth 分别为 4,2,2,2,2,2,2,2,2,5,2,2,2,2,3,其中最薄档 2 在 12 个子区间里担任 min,深档 5 仅在自身子区间,合计 36。
Case 2 · typical: depth-flavoured small example [6, 2, 4, 8, 2, 9]
输入: [[6,2,4,8,2,9]]
期望: 63
六档混合 depth:两个 2 在大量子区间担任 min;总和为 21 个子区间最小值之和。
Case 3 · typical: ascending [1, 2, 3, 4, 5]
输入: [[1,2,3,4,5]]
期望: 35
严格递增 depth:每个子区间最小值都是其左端点。
Case 4 · typical: descending [5, 4, 3, 2, 1]
输入: [[5,4,3,2,1]]
期望: 35
严格递减 depth:每个子区间最小值都是其右端点。
Case 5 · boundary: empty book
输入: [[]]
期望: 0
N=0:没有任何子区间可累加,返回 0。
Case 6 · boundary: single price level
输入: [[7]]
期望: 7
唯一子区间就是 [7] 自身,min=7。
Case 7 · boundary: two levels ascending [3, 5]
输入: [[3,5]]
期望: 11
三个子区间 [3],[5],[3,5] 最小值之和 = 3+5+3 = 11。
Case 8 · boundary: two levels descending [5, 3]
输入: [[5,3]]
期望: 11
三个子区间 [5],[3],[5,3] 最小值之和 = 5+3+3 = 11。
Case 9 · boundary: uniform depth [4, 4, 4]
输入: [[4,4,4]]
期望: 24
全相同 depth=4,6 个子区间,每个 min=4,合计 24。
Case 10 · boundary: uniform depth length 5 [4,4,4,4,4]
输入: [[4,4,4,4,4]]
期望: 60
全相同 depth=4,N=5:5*4*6/2 = 60。
Case 11 · boundary: max depth 1e6 across small book
输入: [[1000000,1000000,1000000]]
期望: 6000000
三个 depth 都达到 1e6 上界;6 个子区间各自 min=1e6 合计 6e6。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: bid_depths [4, 2, 5, 2, 3] (depth-flavoured)
输入: [[4,2,5,2,3]]
期望: 36
15 个子区间的瓶颈 depth 分别为 4,2,2,2,2,2,2,2,2,5,2,2,2,2,3,其中最薄档 2 在 12 个子区间里担任 min,深档 5 仅在自身子区间,合计 36。
Case 2 · typical: depth-flavoured small example [6, 2, 4, 8, 2, 9]
输入: [[6,2,4,8,2,9]]
期望: 63
六档混合 depth:两个 2 在大量子区间担任 min;总和为 21 个子区间最小值之和。
Case 3 · typical: ascending [1, 2, 3, 4, 5]
输入: [[1,2,3,4,5]]
期望: 35
严格递增 depth:每个子区间最小值都是其左端点。
Case 4 · typical: descending [5, 4, 3, 2, 1]
输入: [[5,4,3,2,1]]
期望: 35
严格递减 depth:每个子区间最小值都是其右端点。
Case 5 · boundary: empty book
输入: [[]]
期望: 0
N=0:没有任何子区间可累加,返回 0。
Case 6 · boundary: single price level
输入: [[7]]
期望: 7
唯一子区间就是 [7] 自身,min=7。
Case 7 · boundary: two levels ascending [3, 5]
输入: [[3,5]]
期望: 11
三个子区间 [3],[5],[3,5] 最小值之和 = 3+5+3 = 11。
Case 8 · boundary: two levels descending [5, 3]
输入: [[5,3]]
期望: 11
三个子区间 [5],[3],[5,3] 最小值之和 = 5+3+3 = 11。
Case 9 · boundary: uniform depth [4, 4, 4]
输入: [[4,4,4]]
期望: 24
全相同 depth=4,6 个子区间,每个 min=4,合计 24。
Case 10 · boundary: uniform depth length 5 [4,4,4,4,4]
输入: [[4,4,4,4,4]]
期望: 60
全相同 depth=4,N=5:5*4*6/2 = 60。
Case 11 · boundary: max depth 1e6 across small book
输入: [[1000000,1000000,1000000]]
期望: 6000000
三个 depth 都达到 1e6 上界;6 个子区间各自 min=1e6 合计 6e6。