ARC159 - AtCoder Regular Contest 159

C. Permutation Addition

题意

给出长度为 $N$ 的正整数数列 $A = \{a_1,\cdots,a_N\}$，定义一次操作如下：

• 选择一个 $\{1,\cdots,N\}$ 的排列 $P = \{p_1,\cdots,p_N\}$，更新 $A\gets \{a_1+p_1,\cdots,a_n+p_n\}$

判断是否可以通过不超过 $10^4$ 次上述操作，使得操作后的 $A$ 中每一项都相同。

数据范围：$2\leqslant N\leqslant 50, 1\leqslant a_i\leqslant 50$。

思路

错误的思路二分结果

开始想的是通过二分最终数列 $A$ 中的相同的元素 $a^*$，然后判断新的数列 $b_i = |a_i - a^*|$，是否可以通过排列的求和得到，但是这样构造排列非常困难，无法实现。

题解的直接构造

直接考虑最终状态满足的性质，设 $A$ 中初始全部元素之和为 $S = \sum_{i=1}^Na_i$，由于每次增加一个排列，总和增加 $\frac{N(N+1)}{2}$，所以最终的求和一定是以下总和中的一个

$$S,\ S + \frac{N(N+1)}{2},\ S + \frac{N(N+1)}{2}\cdot 2,\cdots$$

由于最终可以表示为 $N$ 个相同元素求和，不妨令这个元素是 $a^*$，于是 $\exists m$，使得 $N |(S + \frac{N(N+1)}{2})\cdot m$，不难发现，左式等价于 $N | S$ 或 $N |( S + \frac{N(N+1)}{2})$（因为当 $m\geqslant 2$ 时，右侧加的元素中必有 $N(N+1)$ 可消去）

所以有解的充分条件为 $N | S$ 或 $N | (S+ \frac{N(N+1)}{2})$。

下面考虑如何构造出答案，并因此说明上述的条件是有解的充要条件。考虑一种最简单的数列变换，

$$P_1 = \{2,1,3,4\cdots,N\},\\ P_2 = \{N, N-1, N-2, N-3, \cdots,1\}$$

于是将 $P_1$ 和 $P_2$ 加在 $A$ 上，结果是

$$\{a_1+N+2, a_2+N, a_3+N+1,a_4+N+1,\cdots,a_N+N+1\}$$

考虑与原串的变换量，并以 $N+1$ 作为中心轴，则 $N+1 + \{1, -1, 0, 0,\cdots, 0\}$，
所以可以通过上述两个串将 $a_1\gets a_1 + 1$，并 $a_2\gets a_2 -1$。

再考虑最终元素 $a^*$，如果每次只看差值，其实数列的总和一直没有变换，如果 $N | S$，则 $a^* = \text{mean}(A) = S / N = \frac{1}{N}\sum_{i=1}^Na_i$；如果 $N | (S + \frac{N(N+1)}{2})$，则可以先将 $P = \{1,2,\cdots,N\}$ 作用在 $A$ 上，从而转换为第一种形式。

我们只需要考虑每次将所有小于 $a^*$ 的 $+1$，所有大于 $a^*$ 的 $-1$。假设不同时存在一个大于 $a^*$ 和一个小于 $a^*$ 的元素，则与 $a^*$ 是 $A$ 的均值矛盾，所以一定存在一种方法使得每次选择两个元素进行 $+1$ 和 $-1$ 操作，使得最后 $A$ 全部变为 $a^*$。

代码实现上，先判断是否需要补充一个排列，再求出 $a^*$ 并分别保存大于和小于 $a^*$ 的 $a_i$，最后每次从大于的集合和小于的集合中各取一个，输出对应的两个排列。

点击显/隐代码

/*
* File    : C.cpp
* Time    : 2023/04/11 19:33:28
* Author  : wty-yy
* Version : 1.0
* Blog    : https://wty-yy.space/
* Desc    : https://atcoder.jp/contests/arc159/tasks/arc159_c
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <math.h>
#include <vector>
#include <map>
#define ll long long
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int, int>
#define vip vi<pii>
#define mkp make_pair
#define pb push_back
using namespace std;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n, sum = 0;
    cin >> n;
    vi a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    if (sum % n != 0 && (sum + n*(n+1) / 2) % n != 0) {
        cout << "No" << '\n';
        return 0;
    }
    cout << "Yes" << '\n';
    function<void(int, int)> show_permutation = [&](int lower, int upper) {
        for (int i = 1, cnt = 1; i <= n; i++) {
            if (i == lower) cout << n << ' ';
            else if (i == upper) cout << n-1 << ' ';
            else cout << cnt++ << ' ';
        }
        cout << '\n';
        for (int i = 1, cnt = n; i <= n; i++) {
            if (i == lower) cout << 2 << ' ';
            else if (i == upper) cout << 1 << ' ';
            else cout << cnt-- << ' ';
        }
        cout << '\n';
    };
    int mid = (sum % n == 0 ? sum / n : (sum + n*(n+1)/2) / n);
    int total = (sum % n != 0 ? 1 : 0);
    vi lower, upper;
    for (int i = 0; i < n; i++) {
        if (sum % n != 0) a[i] += i + 1;
        total += abs(a[i] - mid);
        if (a[i] < mid) lower.pb(i);
        else if (a[i] > mid) upper.pb(i);
    }
    cout << total << '\n';
    if (sum % n != 0) {
        for (int i = 1; i <= n; i++) cout << i << ' ';
        cout << '\n';
    }
    while (lower.size()) {
        show_permutation(lower.back()+1, upper.back()+1);
        if (++a[lower.back()] == mid) lower.pop_back();
        if (--a[upper.back()] == mid) upper.pop_back();
    }
    assert(upper.size() == 0);
    return 0;
}