比赛地址

先纪念一下ARC第100场!
Tasks
– Linear Approximation
– Equal Cut
– Or Plus Max
– Colorful Sequences (too hard to deal with it)

C – Linear Approximation

Statement

Snuke has an integer sequence $A$ of length $N$.
He will freely choose an integer $b$.
Here, he will get sad if $A_i$ and $b+i$ are far from each other.
More specifically, the sadness** of Snuke is calculated as follows:
$$abs(A_1 – (b+1)) + abs(A_2 – (b+2)) + … + abs(A_N – (b+N))$$
Here, $abs(x)$ is a function that returns the absolute value of $x$.
Find the minimum possible sadness of Snuke.

Idea

输入的时候先把$A_i$减去$i$,然后对新的数组排序,显然满足条件的$b$就是新数组的中位数。

Code

很短很好写,没有特判。

D – Equal Cut

Statement

Snuke has an integer sequence $A$ of length $N$.
He will make three cuts in $A$ and divide it into four (non-empty) contiguous subsequences $B, C, D$ and $E$.
The positions of the cuts can be freely chosen.
Let $P,Q,R,S$ be the sums of the elements in $B,C,D,E$, respectively.
Snuke is happier when the absolute difference of the maximum and the minimum among $P,Q,R,S$ is smaller.
Find the minimum possible absolute difference of the maximum and the minimum among $P,Q,R,S$.

Idea

将数组分成连续的四段,即决定三个分割点,使每一段数字之和尽可能地接近。
$O(n)$枚举第二个分割点,对于每一个不同的位置,都有唯一确定的,分割它左边和右边部分的方案,使得结果对于这个位置最优。发现在第二个点向右移动的时候,第一个和第三个分割点也在不断向右移动。用两个指针处理即可。

Code

E – Or Plus Max

Statement

There is an integer sequence of length $2^N$: $A_0, A_1, …, A_{2^N-1}$. (Note that the sequence is $0$-indexed.)
For every integer $K$ satisfying $1 \leq K \leq 2^N-1$, solve the following problem:

Let $i$ and $j$ be integers. Find the maximum value of $A_i + A_j$ where $0 \leq i < j \leq 2^N-1$ and $(i$ $or$ $j) \leq K$.
Here, $or$ denotes the bitwise OR.

Idea

以下是官方题解:

中文:找到满足条件的前二大的$A_i$和$A_j$,使得$i \ or \ j ⊆ x$。必要条件是$x ⊆ i$和$x ⊆ j$。令$f_x$为满足条件的$i$和$j$,我们只要从小到大枚举$x$,对于每一个x的非零位j,我们可以用$f_x$的值去更新$f_{x|(1<<j)}$。同时维护$f_{x_0}$和$f_{x_1}$(前二大),最后$O(2^N)$更新答案。
时间复杂度$O(N 2^N)$。

Code

Summary

这场比赛没有打完就被电话拖住了。。。
幸好当时没有交题不然又是一题选手(