题解：P14728 [ICPC 2022 Seoul R] Linear Regression

chen_zhe · 2025-12-12 22:09:35 · 题解

这是官方题解的 AI 中文翻译。

算法解析

给定一组数据点 \{(x_1, y_1), \dots, (x_n, y_n)\}，当允许删除其中 k 个点时，要求计算可能的最优线性函数及其误差值。
可以将这些给定的数据视为二维平面上的点，若应用 point-to-line duality（点线对偶原理），该问题可转化为：

在 n 条直线中，寻找一条与至少 n - k 条直线相交的最短垂直线段。

若直接计算 n 条直线的 arrangement A（平面分布结构），并从每个顶点出发考虑所有可能的垂直线段，则需要 \Omega(n^2) 以上的时间，必然导致超时。

因此，应考虑 直线排列（arrangement）中的 level（层次）。
对于介于 1 到 n 的整数 m，定义 A 的 m-level 为：

在该层上方恰好有 m - 1 条直线的所有边（edge）组成的链。

于是：

本题所要求的解法是：
仅计算 1 \le m \le k + 1 的所有 m-level 及 (n - m + 1)-level，并对它们进行 linear scan（线性扫描）。

理论上，存在一个时间复杂度为 O(n \log n + k n) 的算法；
但在实际实现中，更可行的方法如下，其时间复杂度为：

步骤 1

从输入的点集 P 中，计算其 convex layer（凸层） 直到第 k 层。
其中：

• 第 1 层是 P 的 convex hull（凸包）；
• 第 2 层是将第 1 层上的点删除后，剩余点的凸包；
• 如此重复，直到得到第 k 层。

该过程最多需要 O(k \log n) 时间。

步骤 2

利用上一步计算得到的 convex layer，在 P 的对偶直线排列中，
仅计算 (k + 1)-level 与 (n - k)-level。

这一步可以通过 rotational line sweep（旋转扫描） 实现：

• 从 P 中最左侧的第 k + 1 个点经过的垂直线开始；
• 以该点为中心逆时针旋转；
• 每当旋转线经过另一个点时，切换旋转中心；
• 当前旋转中心对应的点，其对偶直线在 (k + 1)-level 中对应一条 edge。

这种方法可通过多种方式高效实现。
若结合 convex layer 使用，则有以下性质：

• 下一个旋转中心的候选点始终来自各层 convex layer 中的至多 2 个点；

因此，总体可在 O(n k^{4/3}) 时间内完成。

步骤 3

利用已求得的 (k + 1)-level 与 (n - k)-level，仅计算对偶直线排列中：

这一步可以通过 plane sweep（平面扫描） 完成：
依次计算各 level 上方与下方线段的交点。

由于：

• 该部分的总复杂度至多为 O(n)；
• 在扫描过程中维护的直线（或线段）数量始终为 k；
  因此可在 O(n \log k) 时间内实现。

步骤 4

对于所有 1 \le i \le k + 1：

• 同时扫描 i-level 与 (n - k - 1 + i)-level；
• 计算每个顶点与对侧直线之间的距离；
• 找出最小值并输出其一半。

此部分耗时 O(n)。

除上述方法外，理论上还存在多种可能方案。
然而，当 n 与 k 的范围受限时，若算法复杂度为 \Omega(n k^2) 或 \Omega(n^2)，则将被视为超时，不会通过评测。

总结
本算法利用几何对偶变换与凸层结构，将删点线性回归问题转化为平面直线排列中的层次最短距离问题，
通过对有限层的扫描与旋转求解，实现在 O(k \log n + k^{\frac{4}{3}} n) 时间内求得最优线性函数误差的高效算法。