VP: AtCoder Regular Contest 128(ARC128)

tony102

2021 年 10 月 21 日

2090 次浏览

1 条评论

1575字数

总结比赛记录

一个更加牛逼的名字：Daiwa Securities Co. Ltd. Programming Contest 2021（AtCoder Regular Contest 128）

ARC好神啊，打不动 /kk /wq (快去刷圣遗物)

## A

想想什么时候要把 Gold 换成 Silver。假如现在有 $x$ 的 Gold，先在第 $i$ 天换成 Silver，再在第 $j$ 天换成 Gold。那么要使 Gold 越来越多，就是要满足：$\frac{A_i}{A_j} > 1, A_j \neq 0$， 也就是 $A_i > A_j$

现在看来这个  $j$ 要通过枚举确定，可是 $O(n^2)$ 过不了。想想这个第 $j$ 天能不能确定，假如 $j > i + 1$，那么在 $(i, j)$ 这一段时间内的不操作可能不优，因为可能哪一天 Silver 兑 Gold 大涨，然后再兑 Silver 的再跌回去。所以 $i \leq j \leq i + 1, i \neq j$，所以 $j = i + 1$

然后只需要判断 $A_{i + 1} > A_i$ 即可。

## B

啊....这个结论题。WA 了两发。

实际上发现，我们可以这样操作。假如我们只操作 $R$  球和 $G$ 球，最终只剩下 $B$ 球。不是一般性，假设 $R \geq G$，没有操作可以使 $R - G \mod {3}$ 的值改变。那么应该要满足 $R \equiv G \mod {3}$。因为操作如下：

1. 把一个 $R$ 球和一个 $G$ 球换成 $B$ 球，共 $G$ 次。
2. 把一个 $B$ 球和一个$R$ 球换成 $G$ 球。
3. 把一个 $R$ 球和一个 $G$ 球换成 $B$ 球。
4. 把一个 $R$ 球和一个 $G$ 球换成 $B$ 球。

这样一共是 $R$ 次操作。

类似地，对最终全部换成 $G$ 球和 $R$ 球的做一遍同样的步骤，比较最小操作数即可。

## C

[Sol](https://atcoder.jp/contests/arc128/editorial/2791)

结论：前面一段全零，后面一段就是后缀平均数。正面看上面，不太想证....(~~不会证~~

## D

首先可以发现，若 $A_i = A_{i+1}$，那么 $(i,i+1)$ 这两个球一定永远都不会被消掉。