# 【AtCoder Regular Contest 100】Solution / Editorial / 题解

Posted on

## 比赛地址

– 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.

### 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)$枚举第二个分割点，对于每一个不同的位置，都有唯一确定的，分割它左边和右边部分的方案，使得结果对于这个位置最优。发现在第二个点向右移动的时候，第一个和第三个分割点也在不断向右移动。用两个指针处理即可。

### 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.