← 返回编程题库
coding-topk-slippage-stable-tiebreak中等免费版2000ms未尝试

TCA 最差 K 笔成交:滑点 Top-K 与到达序号稳定打破并列

TCA Worst-K Fills: Top-K Slippage with Stable Arrival-Seq Tiebreak

开始编码

实现 solution(slippage_bps: list[float], arrival_seq: list[int], K: int) -> list[int]。给定并行数组:slippage_bps[i] 是第 i 笔订单的有符号 bps 滑点(正值=不利成交,负值=价格改善),arrival_seq[i] 是它的(全局唯一、但不一定与数组顺序一致)到达序号。返回按滑点最大排序的前 K 笔订单的原数组下标,并列时按 arrival_seq 较小者优先(旧订单胜出)。输出按排名顺序排列(最差的排第一)。

例:solution([3.5, -1.2, 8.0, 2.1, 8.0, 0.0], [101, 102, 103, 104, 105, 106], 3) 返回 [2, 4, 0]。下标 2 与 4 滑点同为 8.0,2 的 arrival_seq 103 小于 4 的 105,所以 2 排在 4 之前;下标 0(滑点 3.5)排第三。

几个边界:K = 0 返回 []K < 0 视作哨兵同样返回 [](K < 0 的其他行为未定义);K > N 返回全部 N 个下标的完整排序,调用方可以传 K = len(slippage_bps) 拿到完整排名;N = 0 时对任意 K 都返回 []

(-slippage, arrival_seq, idx) 整体排序是 O(N log N) 的简单写法;大小为 K 的最小堆同样的复合键则给出 O(N log K),对极大 N、极小 K 更优。两种方式都在时限内。

实现细节由 stubs/stub.py 提供。

实践背景

收盘后的 Transaction Cost Analysis(TCA)报表会把当日"最差 K 笔成交"挑出来,供交易、风控、合规复盘是路由决策、券商选择还是场所毒性导致了这些异常。滑点以 bps 计,对标到达中间价(或 implementation-shortfall 基准),正值意味着成交价比决策价更差,负值则代表价格改善。买方/卖方台子明确要求并列时是确定性、稳定的打破方式:同一份 blotter 在不同主机上重跑、或数据库部分回放之后再跑,最差 K 笔列表必须逐行一致——否则每日复盘会议会变成"为什么这两笔的顺序变了",而不是去讨论成交本身。把 arrival_seq 当次键(旧订单胜出)反映了"早进单簿的那笔暴露在不利选择下的时间更长,并列时它更应该占据靠前的位置"这一直觉。

约束条件

  • 0 <= N <= 5000,其中 N = len(slippage_bps) = len(arrival_seq)
  • 每个 slippage_bps[i] 为有限浮点数,范围 [-1e6, 1e6];负值代表价格改善,正值代表不利成交
  • arrival_seq[i] 两两不同,取值范围 [0, 1e9];它们在数组中的相对顺序**不保证**单调(输入可能已经被多 shard 跨存储 join 过后重排)
  • K 为整数,范围 [-1, N + 100];K <= 0 返回 [];K > N 返回完整排序
  • 输出为 0-based 下标列表,按排名顺序(滑点最差的排在最前)

样例

Case 1 · statement-example: K=3 picks worst three with stable tiebreak

输入: [[3.5,-1.2,8,2.1,8,0],[101,102,103,104,105,106],3]

期望: [2,4,0]

按滑点 bps 降序排列:index 2 与 4 同为 8.0,arrival_seq 较小者(103)优先,故先 2 后 4;其后是 3.5(idx 0)。最终返回 [2, 4, 0]。

Case 2 · visible: K=0 returns empty list

输入: [[1,2,3],[30,10,20],0]

期望: []

K=0 时直接返回空列表。

Case 3 · visible: equal slippage, arrival_seq NOT in index order

输入: [[5,5,5],[50,10,30],3]

期望: [1,2,0]

三笔滑点同为 5.0,按 arrival_seq 升序:idx 1 (10) < idx 2 (30) < idx 0 (50),故返回 [1, 2, 0]。注意 arrival_seq 与下标顺序无关。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · statement-example: K=3 picks worst three with stable tiebreak

输入: [[3.5,-1.2,8,2.1,8,0],[101,102,103,104,105,106],3]

期望: [2,4,0]

按滑点 bps 降序排列:index 2 与 4 同为 8.0,arrival_seq 较小者(103)优先,故先 2 后 4;其后是 3.5(idx 0)。最终返回 [2, 4, 0]。

Case 2 · visible: K=0 returns empty list

输入: [[1,2,3],[30,10,20],0]

期望: []

K=0 时直接返回空列表。

Case 3 · visible: equal slippage, arrival_seq NOT in index order

输入: [[5,5,5],[50,10,30],3]

期望: [1,2,0]

三笔滑点同为 5.0,按 arrival_seq 升序:idx 1 (10) < idx 2 (30) < idx 0 (50),故返回 [1, 2, 0]。注意 arrival_seq 与下标顺序无关。