• https://atcoder.jp/contests/arc128/tasks
• https://www.bilibili.com/read/cv13612020
• https://www.cnblogs.com/stinger/p/15416806.html

arc 好难。。。（虽然题面都很简单）

A Gold and Silver

著名的套利系列问题，但是这个题应该是里面最简单的一类，可以贪心，
扫一遍就行了。

B Balls of Three Colors

讨论一下最后保留哪个，然后就很容易了。

C Max Dot

先不考虑 𝑚 的限制。。。
考虑 n=2 的情况，如果 a1 < a2 的情况，显然资源全部都给 a2，否则只能对半分。
考虑 n 个数的情况，一定是 0 0 x x x x 这种 pattern，均分给一个后缀。
题解用的是调整法，也不难用归纳法证明，我们可以把后面的后缀合并起来看成是一个数，权值用平均值代替，
然后沿用 n=2 的方法即可。

我们枚举后缀，得到的 x 有可能不满足 m 的限制。
这个时候我们只要先把这些后缀填上 m，然后就可以递归到更短且 s 更小的问题。
这样直接做是 O(n2) 的，可以构造一个 a 递增的序列就可以弄出最坏复杂度。。
不过已经足够通过本题。。。然后题解最后还说仔细观察这个过程可以用凸包优化到 O(n)，
（。。我猜是斜率 DP？。。。没能写出来。。）

const int N = int(5e3) + 9;

int n,m,s;
int a[N];

DB gao(int n, DB m, DB s) {
    vector<pair<DB,int>> avg; DB ss = 0;
    DWN(i, n, 0) {
        ss += a[i];
        avg.PB({ss / (n-i), i});
    }
    int t = max_element(ALL(avg))->se;
    DB x = s / (n-t);
    if (x <= m) {
        DB z = 0;
        FOR(i, t, n) z += x * a[i];
        return z;
    } else {
        DB z = 0;
        FOR(i, t, n) z += m * a[i];
        return z + gao(t, m, s-(n-t)*m);
    }
}

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    RD(n,m,s); REP(i,n)RD(a[i]);
    OT(gao(n,m,s));
}

D Neq Neq

看起来有点像 spoj zuma 那个题。。。不过转移感觉不是很好想。。
首先如果是 x,y,x,y,x … 这样的交错序列，答案就是斐波那契数列，一旦合并之后状态就会被分割。
那么用类似 上次那个题 的方法，可以用 x,x 将状态分割成独立的子问题，最后答案用乘法原理乘起来即可。

考虑不存在相邻元素相等的子问题，考察某个区间能否把中间的元素全部合并掉，
判定的条件是，长度 <= 3 或者这个区间有 3 种不同的元素，因为相邻的元素不同，总是可以用第三种元素作为支点反复消，不难用归纳法证明。

设 f[i] 表示以 i 元素结尾的方案数，有了上面的结论，就可以得到转移方程，大概就是斐波那契关系之上再加点东西，
f[i] = f[i-1] + f[i-2] + pre，其中 pre 是所有符合上述判定的前缀和，注意别和长度 <= 3 的算重复了。
用类似 小z的袜子 里的方法维护区间不同元素的数目即可。

实现的时候，可以设置哨兵 f[0] = f[1], f[n+1] = f[n] 以简化代码。

const int N = int(2e5) + 9;

Int f[N]; int a[N], c[N], cn;
int n;

void add(int x) {
    x = a[x];
    if (!c[x]) ++cn;
    c[x] += 1;
}

void dec(int x) {
    x = a[x];
    c[x] -= 1;
    if (!c[x]) --cn;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    RD(n); REP_1(i, n) RD(a[i]);

    f[0] = 1; f[1] = 1; a[0] = a[1]; a[n+1] = a[n]; ++n;
    Int z = 1, pre = 0;

    int l = 1; REP_1(i, n) {
        if (a[i] == a[i-1]) {
            z *= f[i-1]; f[i-1] = 0; f[i] = 1;
            while (l < i) dec(l++); add(i); pre = 0;
        } else {
            add(i); while (cn > 2 && l < i-2) pre += f[l], dec(l++);
            f[i] = f[i-1] + f[i-2] + pre;
        }
    }
    cout << z << endl;
}

E K Different Values

直接 dfs 显然不行，考虑构造。。。
(1 hour later … )

呃。。。好吧，我觉得这个题还是挺难的。囧。。完全没看懂 题解。。。
但是 标程 到是挺容易丽洁的。。。

我们先考虑 k|n 的情况，那么可以分成 n/k 组，我们尝试贪心构造，每次尽可能放最小的，但是放到后面有可能需要回溯。。。
看来我们需要想一种贪心构造，使得问题的规模不断减小，并且最好不会出现回溯。。

设 n = dk + r，(r > 0)，首先如果存在 Ai > (d+1) 或者有超过 r 组 == (d+1) 那么显然无解 (a)，
否则，如果恰好有超过 r 组 == d+1，那么从这 r 组里选最小的 (1)，否则选全局最小的 (2)，添加到队首，
当然选出的数要保证与上次出现的距离至少为 k，然后递归到 n-1 即可。

上面的过程显然保证字典序最小，我们只要证明这个算法一定能终止即可。。
考虑反证法 + 归纳法。。

首先如果第一轮没有出现无解的情况，那么后面的轮次也都不会出现。。否则前面轮次的 (1) 就已经取走了。
再考虑如果某个轮次没有取到数，那么前 k 轮次时也一定没有取到数，但是 <= k 轮次时一定可以取到数，
因此取不到数的情况也不存在。

F Game against Robot

非常赞的组合计数题。有早年 SRM Div1 1000 的感觉了。。。。

首先考虑静态的问题，然后类似 linearity of expectation，我们设法求出每个 Ai 在结果中出现的次数。
我们只关注排列中每个元素和 Ai 的大小关系，这样只需要考察 01 序列，最后对贡献乘以 i!(n-i)! 即可。

进一步考察静态过程，我们可以计数得到所有大于等于 Ai 的数在答案中的出现次数，类似那个证明 Catalan 数等于 \binom{2n,n} – \binom{2n, n+1} 的过程，最后预处理二项式系数的和即可。

具体得看 lyric 的代码。