题解 P4791 【[BalticOI 2018]蠕虫之忧】

### Worm Worries ### 蠕虫之忧 **翻译自 [BalticOI 2018 Day 1 题解](https://boi2018.progolymp.se/spoiler-day1.pdf)** 这个问题实际上是一个“三合一”问题，分别对应一维、二维和三维的情况。 以下所述大部分程序都能通过所有数据，但是为了减少查询次数，对于子任务 2、4 和 6，这三个子任务需要使用单独的算法来解决（边界数据）。 1. 对于只有一维的数据，我们可以首先尝试类似二分查找的算法。以 $N\times1\times1$ 的坐标系为例，我们可以通过以下方式将问题的规模减小：询问中间两个点的参数值，即 $H[N/2]$ 与 $H[N/2+1]$。如果 $H[N/2]\geqslant H[N/2+1]$，那么我们可以将搜索区间设置为数组的前半部分（包括第 $N/2$ 个元素），否则将搜索区间设置为后半部分。 然而对于 $N=1\,000\,000$ 的数据，这种算法需要查询 $40$ 次，而第 2 个子任务要求查询次数最多为 $35$。我们需要使用另一种算法将查询次数降低到 $35$，这种算法基于_黄金分割搜索_。 考虑我们要在区间 $[a,\,b]$ 内找到一组解，如果 $a=b$，我们只需要返回 $a$。否则我们需要查询区间中点 $m$ 和 $m+1$，根据 $H[M]$ 较大还是 $H[M+1]$ 较大，递归地在区间 $[a,\,m]$ 或 $[m+1,\, b]$ 中寻找一组解。但是我们并**不**需要保证要查询的点 $m$ 和 $m+1$ 一定相邻：假设我们查询的两个点 $x$ 与 $y$ **不**满足 $x<y$。再强调一次，如果 $H[x]\geqslant H[y]$，我们可以在区间 $[a,\,y-1]$ 中递归求解，否则我们在区间 $[x+1, b]$ 中递归求解。但是当我们在区间 $[a,\,y-1]$ 中递归求解时，我们已经在一开始查询了区间内的一个点 $x$ 的参数，所以我们在下一步只需要再查询另外一个点的参数。为了理解为什么这样递归求解会产生一组解，请注意在这个过程中你最终找到的点会是所有查询过的点中参数最大的一个。 为了找到正确的 $x,\,y$ 作为起点开始查询，我们使用黄金分割率 $\phi=\frac{1+\sqrt{5}}{2}$，或者是它的逆 $\frac{\sqrt{5}-1}{2}\approx0.618$。如果我们令 $x=0.618a+0.382b$ （四舍五入至最接近的整数）、$y=0.382a+0.618b$ 作为起点，并在区间 $[a,\,y-1]$ 内递归求解，则 $x\approx0.382a+0.618(y-1)$，所以选取的中点将始终粗略地在同一黄金分割率附近。 这个算法需要查询 $29\approx\log_\phi N$ 次，而二分搜索需要查询 $40\approx\log_2N$ 次。 2. 对于含有两维的测试数据，我们可以重复利用在一维空间内二分搜索的一些思路。我们可以查询将矩形划分为两部分的直线上的点的参数值。考虑这些值中的最大值，并且也要考虑最大值左右两个相邻点的值（假设直线垂直于这个二维平面）。如果它们都小于等于最大值，那么这个点就是一个有效解。否则，我们可以向参数值上升的一侧递归求解。直观上，如果我们继续向越来越大的一侧查询，我们将不会重复经过任何一条直线，因为我们将要经过的所有点都比这条线上的点的参数大。这种做法有一些细节需要注意。我们需要保证如果之前查询过的最大值大于当前扫描线上的值，则向之前查询过的最大值的一侧递归查询，否则我们在一个子矩形中找到的一组解不一定是整个矩形中的解。假设你交替的在水平方向上和竖直方向上划分平面并且实现正确的话，你就能够通过子任务 3 和 4。这个算法也能推广到一维空间和三维空间，可以通过子任务 1 和 5。 3. 一个原始的想法是，随机查询一些点，找到最好的一个，在这个题中就是参数值最大的一个。另外一个原始的想法是从一个随机点出发，查询相邻的点，并且向参数值增加的方向移动，直到找到一组解。 这两个想法都可以被卡掉，但是它们可以组合成一个算法：先随机查询 $Q/2$ 个点，然后选择最好的一个，向参数值上升的方向移动，直到找到一组解。 为什么这样做能过掉这道题呢？假设在第一阶段你找到了前 $Q/12$ 好的一个点。接下来你为了向更优的点移动时，你最多需要移动 $Q/12$ 步。每一步你可能需要查询最多 $6$ 次（如果你的实现够优的话，平均 $3$ 次），所以你在第二阶段需要进行 $Q/12\cdot6=Q/2$ 次查询，这意味着，总共进行了 $Q$ 次查询。 找不到这样的一个点的概率最大为 $$\left(1-\frac{Q}{12NMK}\right)^{Q/2}\approx\exp\left(-\frac{Q}{12NMK}\frac{Q}{2}\right)=\exp\left(-\frac{Q^2}{24NMK}\right).$$ 对于子任务 6，失误的概率小于 $\frac{1}{1800}$。这个算法也适用于子任务 1、3 和 5。 有关这道题目的一些有趣的事实： - 这道题目的交互器有 900 行，实现了 14 个不同的数据生成函数（按查询的需要调用）。其中包含了随机测试数据、空间填充曲线、螺旋线、连续下降的线段和像是随机放缩的 $\sqrt{x}$ 和锯齿形等有趣的一维函数。 - 我们原本打算将子任务扩展到四维空间，但是最终放弃了。如果有人想要四维空间的随机空间填充曲线，请联系出题人。 - 显然这个问题已经被计算机科学家研究得很透彻了，并证明了解决这个问题的算法复杂度上下界，两篇论文见下： * https://arxiv.org/abs/quant-ph/0504085 * https://epubs.siam.org/doi/pdf/10.1137/S0097539704447237