# AtCoder Beginner Contest 145

Updated:

AtCoder Beginner Contest 145

• Review: 2020-06-08

# Solutions

## A - Circle

Just flush $r ^ 2$.

## B - Echo

Just judge if $N$ is even and $S.substr(0, N / 2) = S.substr(N / 2, N / 2)$.

## C - Average Length

### Solution 1

Try all the possibilities as they indicate us to.

### Solution 2

Fix a pair $(i, j)$. How many times the road between $i$ and $j$ appears in $N!$ paths> The answer is $2 \times (N - 1)!$.

Therefore, the answer is $\frac{1}{N!} \sum _ {i = 0} ^ {N - 1} \sum _ {j = i + 1} ^ {N - 1} \lvert p _ i - p _ j \rvert \times 2 \times (N - 1)! = \frac{2}{N} \sum _ {i = 0} ^ {N - 1} \sum _ {j = i + 1} ^ {N - 1} \lvert p _ i - p _ j \rvert.$

## D - Knight

### Solution

First of all, we can determine the number of knight’s moves; $(X + Y) / 3$ times. If $(X + Y) \% 3 \neq 0$, the answer is $0$.

To put it simply, we investigate the tour $(0, 0) \mapsto (A, B)$ with $A = X - T$ and $B = Y - T$ by the step $(+1, 0)$ and $(0, +1)$ instead of the original one $(0, 0) \mapsto (X, Y)$ by the step $(+2, +1)$ and $(+1, +2)$. Of course we have to check whether $A, B \geq 0$. The number of the possibilities is $\displaystyle \begin{pmatrix} A + B \\ A \end{pmatrix}$.

## E - All-you-can-eat

### Observation

First of all, given a subset $X$ of $\{ A _ i \}$, how can we determine whether we can eat them all? Since the subset is fixed, the best strategy is exclude the max element of $X$, i.e., $\sum _ {A _ i \in X} A _ i - \max _ {A _ i \in X} A _ i < T$.

In addition, this problem is very near to the well-known knapsack problem.

$DP[i] =$ the maximum value we can eat within $i$ minutes.

We want to try all $A _ i$ as the max element. Hence, we sort $\{ (A _ i, B _ i) \}$ by $A _ i$’s ascending order. We fix one $A _ i$ as the maximum element. Then we calculate $DP$ by using $[0, i)$ elements. Therefore the best possible choice is attained by $DP[T - 1] + A _ i$.

### DP part

The definition is described above.

#### Initial State

$DP[i] = 0$ for all $0 \leq i < T$.

For $k = 0, \dots, N - 1$, first we update $ans \gets \max(ans, DP[T - 1] + B).$ Then, we calculate DP table. For $i = T - 1 - A, \dots, 0$, we execute $DP[i + A _ k] \gets \max(DP[i + A _ k], DP[i] + B _ k).$ Don’t forget to update the DP table not to miss the chance that we will gain better point in less time: For $i = 0, \dots, T - 2$, we execute $DP[i + 1] \gets \max(DP[i + 1], DP[i]).$

## F - Laminate

We promise that we adopt $1$-indexed on $H _ i$ and we insert $H _ 0 = 0$ and $H _ {N + 1} = 0$.

### Observation

First of all, we have to notice the following relation.

Lemma F.1: The total number of the manipulation is $S = \sum _ {i = 0} ^ {N} \max\left(0, H _ {i + 1} - H _ i \right).$

Proof. Just count each range by the right side edge.

Next we have to consider the manipulation that enable us to choose at most $K$ columns and change the value of $H _ i$ for arbitrary integer for each columns. We state the lemma.

Lemma F.2: Let $1 \leq k \leq N$. When we change the value of $H _ k$, the value $S$ attains its minimum if we choose $H _ k = H _ {k - 1}$.

Proof. We separate the situation into two cases.

The case $H _ {k - 1} \leq H _ {k + 1}$: we have to overcome the difference of height; $H _ {k + 1} - H _ {k - 1}$, i.e., $\max(0, H _ k - H _ {k - 1}) + \max(0, H _ {k + 1} - H _ k) \geq H _ {k + 1} - H _ {k - 1}.$ The equality holds if we choose $H _ k = H _ {k - 1}$, i.e., $\max(0, H _ k - H _ {k - 1}) + \max(0, H _ {k + 1} - H _ k) = 0 + (H _ {k + 1} - H _ k) = H _ {k + 1} - H _ {k - 1}.$

The case $H _ {k - 1} \geq H _ {k + 1}$: it follows that $\max(0, H _ k - H _ {k - 1}) + \max(0, H _ {k + 1} - H _ k) \geq 0.$ The equality holds if we choose $H _ k = H _ {k - 1}$, i.e., $\max(0, H _ k - H _ {k - 1}) + \max(0, H _ {k + 1} - H _ k) = 0 + 0 = 0.$

Lemma F.3: Suppose that we can execute the manipulation in $K$ times. Then, the minimum value of $S$ is equal to the minimum value of $S$ when we choose $N - K$ elements in $\{ H _ i \}$.

Proof. By Lemma F.2, the best strategy is change the value of $H _ k = H _ {k - 1}$. Therefore, each manipulation is regarded as deleting one elements. Then, the statement follows.

### DP part

By Lemma F.3, we convert this problem into DP.

#### Definition

$dp[i][j] =$ the minimum value of $S$ so far; the last element we have chosen is $i$ and we have chosen $j$ elements.

#### Initial State

$dp = 0$, otherwise $dp[i][j] = \infty$.

The last element we complete the journey is arbitrary. Then, the answer is $\min _ {0 \leq i \leq N} dp[i][N - K].$
For $i = 1, \dots, N$, for $j = 1, \dots, N - K$, we try to connect $k$ and $i$ for all $k < i$, i.e., $dp[i][j] = \min _ {0 \leq k < i} \left( dp[k][j - 1] + \max\left(0, H[i] - H[k] \right) \right).$