Archery解题报告

IOI2009 Day1

题目叙述

一场箭术比赛规则如下所示。在一条直线上排着N个靶子，靶子从左到右序号依次为从1到N。同时有2N个选手，在比赛的任何时刻，同一个靶位上都有两个选手。比赛的每一轮按照如下规则进行：

在同一个靶位的两位选手比赛一场决出胜者，然后所有选手按照如下规则移动：

在2到N号靶位上的胜者移动到他们的左侧的靶位（即分别移动到1到N-1号靶位）

在2到N号靶位上的负者，以及1号靶位上的胜者，停留在同一个靶位。

1号靶位上的负者移动到N号靶位。

这场比赛持续R轮（R>=2N）。

你作为唯一一个准时到达的选手（其他选手已经提前到达了并且排成了一行），你现在要做的就是插入这个队伍，在你进入队伍后，队列中前两个选手将对应一号靶位，接下来两个将对应二号靶位，以此类推。

所有的选手（包括你）都用一个数值衡量技术水平，在同一个靶位上，数值比较小的选手会成为胜者，没有两个选手的技术水平相同。

在了解了所有选手的技术水平之后，你需要找到一个位置插入使得你最终对应的靶位序号尽量小，在此前提下，你希望你初始时对应的靶位序号尽量大。

数据规模

1<=N<=200000

2*N<=R<=1000000000

解题思路

整个算法的描述非常长，但其中的思想并不是那么复杂，算法步骤可以总结为以下几步：

1. 一个朴素的模拟思路可以给出一个O(N2R)时间复杂度的算法。

2. 可以观察到经过不超过2N轮，整个比赛变成一个长度为N循环，这可以让模拟思路的时间复杂度降低至O（N3）

3. >我们可以将比赛的模拟过程从O(N2)降低至O(N)（在我们选定初始位置以后），这一部分是整个解答中最复杂的一部分，其中的关键在于我们只关心自己的位置，而并不关心其他人的。

4. 当我们可以在选定开始位置之后模拟出结束位置，我们可以通过一个略微修改的二分搜索将整个算法由O(N2)降低至O（NlogN）。

优化至O(N3)

考虑编号为N+2到2N的选手，我们称他们为弱者。

定理1

经过若干轮比赛，所有弱者会占据2到N号靶场，每个位置一个选手，并且在接下来的比赛中不会移动

证明

在N-1轮之后，1号选手会占据1号靶位并且停留在那里不动，从那时开始，我们考虑N-1位弱者加上1号选手共N位选手构成的集合（我们称之为weak+1集合），我们假设N个靶位围成了一个圆圈，我们有如下性质：

当一个weak+1集合内的选手和一个weak+1集合外的选手比赛时，weak+1集合内的选手保持不动而weak+1集合外的选手会向左方移动

当两个weak+1集合内的选手比赛时，其中一位不动，另一位向左方移动。

引理1

在1号选手到达1号靶位之后不超过N轮，所有靶位上都至少有一个weak+1集合内的选手。

证明

假设上面结论是错误的，我们知道如果有一个靶位被一个weak+1集合内的选手占据后，它将一直被一个weak+1集合内的选手占据。所以如果引理1是错误的，那么一定存在一个靶位从来没有被weak+1集合内的选手占据过（在N轮之内），我们称之为靶位A。如果A从未被weak+1集合内的选手占据过。那么靶位A左边的靶位（我们称之为靶位B）将在一轮后仅剩之多一个weak+1集合内的选手，然后两轮后，靶位B左边的靶位将仅剩至多一个这样的选手，依次类推，N-1轮后，A靶位左边的N-1个靶位上将至多只剩一个weak+1集合内的选手，而由于一共有N个weak+1集合内的选手，因此A靶位内至少需要有一个这样的选手，这与假设矛盾，因此引理1是正确的。

现在我们知道，在2N轮之内每个靶位上都至少会有一个weak+1集合内的选手，并且一旦一个靶位上被一个weak+1集合内的选手占据后，它就会一直保持被weak+1集合内的选手占据，由此我们证明了定理1。

我们考虑不在weak+1集合内的选手，因为每个靶位上刚好有一个weak+1集合内的选手，因此每个靶位上都刚好有一个非weak+1集合内的选手。在这种情况下，每个weak+1集合内的选手都会保持不动，因此2到N+1号选手会进行环状运动，每N轮循环一次。

也就是说，如果我们将R替换为R’=2N+(R mod N)，我们将得到同样的答案（记得R>=2N）

上述结论说明我们可以轻易将O（N2R）的算法简化到O(N3)。

优化至O(N2)

现在，当我们选择起始靶位并模拟R’轮之后的情况时，我们做了O(N2)的计算，我们可以用如下方法将其降低至O(N)。

我们注意到一共有三类选手，比我们强的，我们称之为黑色选手，比我们弱的，我们称之为白色选手，而我们自身则称为灰色选手。为了解决问题，我们并不需要搞清楚同色选手之间的差别（这对最终结果没有影响），如果同色的两个选手决出胜负，谁胜谁负对于最终结果没有影响（对灰色选手的最终位置没有影响），而且我们知道当两个不同色的选手比赛时，颜色较暗的一方取得胜利。

那么现在有三种情况，我们分别解决。

情况1

没有黑色选手。也就是说我们是最强的选手，很显然我们应该从N号靶位开始。

情况2

有至少一个黑色选手，但不超过N个，这意味着我们的序号在2到N+1之间，也就是说我们是处在不断循环的选手中。在这种情况下，我们无需观察整个比赛，而仅需观察靶位1。如果我们知道每一轮谁在1号靶位上进行比赛，那么我们仅需观察灰色选手在2N到3N轮之间的何时在1号靶位上进行比赛，我们也就知道了灰色选手最终的位置。我们用如下算法追踪1号靶位上的事件：

我们给每个选手定义一个数值Pi，表示i号选手在1号靶位上比赛可能的最早时间。初始时每个Pi等于他所在的靶位号，然后我们用如下方法模拟赛程：

1. 我们找出谁会在1号靶位上比赛，第一个选手显然是上一轮1号靶位的胜者（或者初始时最左侧的选手）。我们用如下方法找出他的对手：我们找出所有Pi小于等于当前轮数的选手，其中最强的一个将会在1号靶位上进行比赛（这一方法的正确性证明将在下面给出）

2.我们给两者中的负者的数值Pi更改为当前轮数（刚刚过去的）加N，这也是该选手能到达1号靶位的最早可能时间。

让我们来证明上述算法是正确的。我们用Aj表示第j轮在1号靶位上，但j-1轮在2号靶位上比赛的选手。对于每个选手对应的数值Pi，如果他一直在没有输过，那么他最终会成为 。那么现在我们考虑通过上述算法选出的某个Aj（我们用W表示他）。令S=j—Pw。如果S等于0，这也就意味着W不可能成为Aj-1，即使他赢了所有比赛。因此在这个循环中，W永远没有和Aj-1（以及之前的A）相遇的可能。由于W和之前的那些选手永远不会相遇，并且他比其他可能成为Aj的选手都要强，也就是说，他在到达1号靶位之前不会输，也就是说他就是Aj。

如果S大于0，这也就是说W有机会成为Aj-1但却失去了这个机会。那么一定存在一个时刻，W如果赢得接下来全部的比赛，他就可以成为Aj，此时，情况类似于上文。同理可以证明他就是Aj。

那么我们我们对1号靶位的维护已经证明是正确的了，我们来分析下这个算法的时间复杂度。由于同种颜色的选手之间没有差别，所以我们对于任何选手的集合只需要用3个数表示：集合中的黑色，灰色，白色的选手数。因此对于该算法的每一步模拟，我们只需要进行常数次运算。另外我们至多只需要进行3N次模拟，所以总时空复杂度为O(N)。

情况3

有超过N个黑色选手，这也就意味着我们是那些最终停留在一个靶位的选手中的一个。我们只需要确定这个靶位是哪个。

我们已经证明了当1号选手到达1号靶位之后，所有weak+1集合内的选手所做的事情就是在靶位之间互相推，直到所有选手都停在了不同的靶位上，由于我们的编号大于N+1，所以所有白色和灰色的选手都属于weak+1集合，所以我们只需要模拟灰色和白色选手互相推的过程。我们从1号靶位开始，这里不允许任何灰色或者白色选手停留。然后我们试图计算在圆圈上移动过每一个靶位的选手数目有多少。初始时，从1号靶位被推到N号靶位上的选手就是初始在1号靶位上的选手（此时我们的计数只是一个下界，等下我们也许会发现更多从1号靶位被推到N号靶位上的选手数目），然后我们移动到N号靶位，我们向待安定的选手集合中加入N号靶位上的所有选手，然后再留下一个选手在N号靶位（如果有白色选手，我们就会把他留下，否则就留下灰色选手，如果集合是空的，显然我们不留下任何选手，让黑色选手占据这个靶位）。我们继续沿着圆圈走，从N到N-1，从N-1到N-2。在每个靶位，我们“捡起”所有灰色和白色选手，然后留下一个选手。最后我们走回了1号靶位，如果我们仍然有选手需要从1号靶位移动到N号靶位，那么我们只需重复一次刚才的步骤。当我们第二次到达1号靶位时，必然没有任何选手需要从1号靶位移动到N号靶位，这是由于根据定理1，经过2N轮比赛之后，所有灰色或者白色选手都会安定在一个靶位上。这个算法的时空复杂度都是线性的。由于我们只在必要时移动选手，并且能保证每个灰色或者白色选手能够安定在一个靶位直到比赛结束，所以这个算法也是正确的。

以上优化令我们对于比赛的模拟从O(N2)降低到了O(N)，从而使整个解法的复杂度由O(N3)降低到了O(N2)

优化至O（NlogN）

对于本题的最后一步优化是基于著名的二分检索算法，上文描述的快速模拟算法可以很容易计算出灰色选手一共多少次从1号靶位移动到了N号靶位（设这一数字为T）。结合灰色选手的最终位置（设这一数字为X）可以让我们从一个线性的尺度下观察最终的位置。如果我们用X—N×T来表示模拟算法的结果的话，我们可以认为灰色选手每移动一次位置就会使答案减1。然后如果我们观察上述模拟算法，我们就可以发现，如果初始位置更高一些，最终的结果不会更低，举例来说，如果你开始时的P数值大一些的话，那么你最终的位置不可能比较小的P数值所得的最终位置更靠前（在线性的尺度下）。

有了这个开始位置和最终位置之间的单调关系之后，我们就可以利用如下算法找到最佳的开始位置：

1. 计算从1号靶位开始的最终位置

2. 计算从N号靶位开始的最终位置

3. 二分查找每一个比N的倍数大的最小的最终位置

4. 从上述选出的开始位置中选择一个最好的作为答案

由于二分查找的范围是O(N)的，每次查找最多只需要O(logN)次询问，又因为最多需要O(1)次查找，每次询问的复杂度为O(N)，所以最终的时间复杂度为O(NlogN)。