题解

思路推导

按评分从大到小记参赛者。一个已确定结果的前缀中，当前冠军必为该前缀评分最高者。考虑当前最大的尚未处理评分 $a_i$。若其后有若干评分落在 $[a_i-k,a_i]$ 内，它们不能在冠军为 $a_i$ 时直接出场，否则该场胜负无法确定。这些“冲突选手”必须在更高评分的冠军尚在场时被消去。

令 $dp_i$ 表示已经安排了前 $i$ 个最高评分选手，并保持所有已发生比赛均可预测的排列数。设第 $i$ 个位置之后连续有 $c$ 个评分与 $a_i$ 的差不超过 $k$。状态有两种转移：把 $a_i$ 插入已有序列的非首位置，有 $i$ 种；或在更高冠军保护下连同这 $c$ 人一起安排，排列因子为 $(i+c-1)!/(i-1)!$。冲突区间右端随着 $i$ 单调移动，可用双指针求出。

做法

子任务 1 枚举所有参赛者排列，逐场模拟并检查评分差。

子任务 2 沿用上述动态规划，对每个 $i$ 线性扫描求冲突区间右端，复杂度为 $O(n^2)$。

满分做法预处理阶乘和逆阶乘，以双指针维护第一个满足 $a_j<a_i-k$ 的位置，并进行两类转移。

正确性证明

对任一前缀，若所有比赛结果可确定，则胜者始终是前缀中评分最高者，因为每次可确定的比赛都由评分较高者获胜。因此，评分与当前最高者之差不超过 $k$ 的选手，只有在某个更高且与其评分差大于 $k$ 的冠军仍在场时才可被确定地淘汰。

按评分递减处理到 $a_i$ 时，所有与它冲突且尚未处理的选手恰为其后的连续 $c$ 人。若不在此时处理这组人，则把 $a_i$ 放入已有合法序列的非首位置，共有 $i$ 个位置；若处理，则这 $c$ 人必须与 $a_i$ 一并放入由此前更高冠军保护的区段，新增元素的相对安排数为 $(i+c-1)!/(i-1)!$。两类情况由是否此时清空冲突组唯一划分且互不重叠，覆盖全部合法排列。初始只有最高两人评分差大于 $k$ 时才存在一个合法起始顺序。归纳可得 $dp_n$ 正好统计所有合法排列。

复杂度分析

子任务 1 为 $O(n!\,n)$；子任务 2 为 $O(n^2)$；满分算法时间复杂度 $O(n)$，空间复杂度 $O(n)$。