「PA 2020」Punkty rankingowe 题解

算法思路

本题使用构造性算法和前缀和性质来解决序列还原问题。核心观察是最大子段和序列必须满足特定的单调性和可加性条件。

关键数学性质

1. 前缀和定义

设 $s_i$ 为前 $i$ 场比赛的 rating 变化总和，则：

• $a_j = \max_{0 \le k \le n-j} (s_{k+j} - s_k)$

2. 必要条件

对于任意 $1 \le j \le n$，最大 $j$ 项和 $a_j$ 必须满足：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++)
        if (a[i] > a[j] + a[i - j]) {
            cout << "NIE\n";
            return 0;
        }
}

数学解释：$a_i \le a_j + a_{i-j}$ 对于所有 $1 \le j < i$

3. 充分构造

当上述条件满足时，可以直接构造解：

for (int i = 1; i <= n; i++)
    cout << a[i] - a[i - 1] << " \n"[i == n];

其中 $a_0 = 0$，因此第 $i$ 项的变化量为 $b_i = a_i - a_{i-1}$

算法正确性证明

必要性证明

如果存在 $i, j$ 使得 $a_i > a_j + a_{i-j}$，则矛盾：

• 考虑长度为 $i$ 的最大子段，可以将其分割为长度为 $j$ 和 $i-j$ 的两段
• 这两段的和最多为 $a_j + a_{i-j}$，矛盾于 $a_i$ 是最大和

充分性证明

当 $a_i \le a_j + a_{i-j}$ 对所有 $j < i$ 成立时，构造的序列满足：

• 前 $i$ 项的和恰好为 $a_i$
• 任意连续 $j$ 项的和不超过 $a_j$

代码解析

输入处理

int n;
cin >> n;
for (int i = 1; i <= n; i++)
    cin >> a[i];

可行性检查

for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++)
        if (a[i] > a[j] + a[i - j]) {
            cout << "NIE\n";
            return 0;
        }
}

构造输出

cout << "TAK\n";
cout << n << "\n";
for (int i = 1; i <= n; i++)
    cout << a[i] - a[i - 1] << " \n"[i == n];

复杂度分析

• 时间复杂度：$O(n^2)$，对于 $n \le 300$ 完全可行
• 空间复杂度：$O(n)$