Google Code Jam 2021 Qualification Round 题解(P1

由于 \(x, y \ge 1\) ，所以要尽可能地少让 CJ 和 JC 出现。

对于连续的一段 ? ，肯定是都填相同的字符，代价最小。原因是可以证明这样填至多产生一个新的代价。

如果其两端为相同字符，或者其中一端是开头或者结尾，那么可以不产生新的代价。

如果其两端为不同字符，那么新产生的代价其实是固定的，比如 C???J ，全填 C 的话需要额外 \(x\) 的代价，全填 J 也需要额外 \(x\) 的代价。 J???C 同理。

遍历一下分类讨论就完事了。

此时，由于 \(x, y\) 可能是复数，所以在某些情况下可能需要尽可能多的让 CJ 或者 JC 多出现。

感觉这其实是比较明显的DP题。 \(dp_{i, j}\) 表示仅考虑前 \(i\) 个字符，第 \(i\) 个字符为 \(j\) 的最小代价。转移方程为：

\[dp_{i, j} = \min_k \{dp_{i -1, k} + cost(k, j)\} \]

Reversort Engineering

可以直接 \(O(N!)\) 枚举所有排列，再用T1中的方法看当前排列的操作数是否和 \(C\) 相同。

首先，每次翻转操作数至少为1，所以 \(C \ge N - 1\) 。

其次，每次翻转操作数至多为 \(N - i + 1\) ，所以 \(C \le \frac{(n+2)(n - 1)}{2}\) 。

假设现在执行第 \(i\) 次操作，剩余操作次数为 \(K\) ，当前操作长度为 \(L\) 。

那么要给之后的每次操作至少留 \(1\) 的余量，所以 \(L \le K - (N - 1 - i)\) 。

又因为剩余长度为 \(N - i - 1\) ，所以 \(L \le N - i - 1\) 。

为了防止后续操作多用不完的情况，且已经保证了后续操作足够多，所以让 \(L\) 尽可能地大，取 \(L = \min(K - (N - 1 - i), N - 1 - i)\) 。

现在知道了每一步的操作长度，且知道了最终的数组，那么逆序操作一遍就可以得出原来的数组。

可以通过一个类似快排的过程求解。期望的次数大概是 \(O(N\log_3N)\) ，实际测试的时候大概是在160次左右。

假设当前需要排序的数组为 \(a\) 。如果 \(|a| \le 2\) ，那么 \(a\) 已经有序了，只是方向不确定，可以直接返回。

利用所给操作实现一个Partition方法，将待排序数组分成前中后三段，段内元素可以乱序，但段间是有序的。

然后就可以递归对3段分别进行排序。

现在是3段段内有序且段间有序的数组，但是每段的方向并没有确定。此时以中段的方向为标准，对前段和后段的方向进行校准。

最后将3段用向有序的段拼接起来就得到了一个有序数组。

此时， \(|a| \ge 3\) 。

取 \(a_0\) 和 \(a_1\) 为Pivot，对 \(a\) 中其余元素 \(x\) ，执行 \(r = Query(a_0, a_1, x)\) 。根据返回值的不同可以确定 \(x\) 在哪一段。

下面以前段为例。

若 \(|P| \le 1\) ，那么其方向并没有意义。

否则，令 \(r = Query(P_0, P_1, a_0)\) ，若 \(r \ne P_1\) ，则说明 \(C\) 和 \(P\) 方向不同，需要将 \(P\) 翻转。

作弊者的分数应该会倾向于更高，可以认为最高分的人是作弊者。

这样就能过Test Set 1了。

假设没有作弊者。那么对于一个选手而言，他的分数越高，他的Skill应该也越高。根据这个就可以推测选手的Skill。因为本题选手的Skill是随机生成的，不妨将选手按分数排序，然后将 \([-3, 3]\) 区间以均分成 \(N\) 分，依次赋给选手。

由于作弊者会以0.5的概率作弊，所以根据上述方法推作弊者的Skill，其Skill相比真实值会偏高。

类似地，问题的Difficulty也可以这么处理推出。

现在，可以根据逆推出的值计算选手作对题目的概率。

如果一个选手做对一道题的概率很高，但是他却没有做对，这样其实是不太正常的，即选手的Skill可能偏高了。如果上述情况发生较多次，那么有理由怀疑这个选手是作弊者。

定义一个选手的可疑程度为他大概率能做对，但却做错了的题数。如果选择最可疑的选手为作弊者，准确率能够达到70%左右。

有的时候，可能作弊者本身的Skill也比较高，导致推测的Skill相比真实Skill差别不大。这个时候每个选手的可疑程度相近，上述方法检测出来的可能不是作弊者。但是，这个时候作弊者的分数应该会非常高，所以可以取分数最高的选手为作弊者。现在就能过了。

多调调参，总能卡过去的。