AtCoder Beginner Contest 145
Updated:
- Review: 2020-06-08
Source codes
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$.
Transition and Answer
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][0] = 0$, otherwise $dp[i][j] = \infty$.
Answer
The last element we complete the journey is arbitrary. Then, the answer is \[ \min _ {0 \leq i \leq N} dp[i][N - K]. \]
Transition
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). \]