AtCoder Beginner Contest 153
Updated:
- Review: 2020-06-16
Source codes
Solutions
A - Serval vs Monster
Flush $(H + A - 1)/A$.
B - Common Raccoon vs Monster
Flush whether $H \leq \sum _ {i} A _ i$ or not.
C - Fennec vs Monster
Without loss of generalities, we can assume that $\{ H _ i \}$ is in the ascending order. We should attack for $H _ 0, \dotsm H _ {N - K - 1}$. The answer is the sum of them.
D - Caracal vs Monster
We can solve this by recursion or direct calculus.
Recursion
We define $f(H)$ as follows.
\[
f(H) = \begin{cases}
1 & H = 1, \\
1 + 2 f(H/2) & \text{otherwise}.
\end{cases}
\]
We flush $f(H)$.
Direct calculus
Let $high$ be the maximum bit up. For example the $high$ of $4$ is $2$. The answer is $2 ^ {high + 1} - 1$.
E - Crested Ibis vs Monster
This is solved by simple DP.
DP part
Definition
$DP[j] = $ the minimum total magic point to gain the total attack point $j$.
Here we regard $DP[H]$ is the minimum point to beat the monster whose health is $H$.
Initial state
$DP[0] = 0$, otherwise $\infty$.
Answer
$DP[H]$.
Transition
Here, we can use the same magic repeatedly as many times as we like. Therefore, we execute the transition by $j$’s ascending order.
For $i = 0, \dots, N$, for $j = 0, \dots, H - 1$, \[ DP[\min(j + A _ i, h)] \gets \min(DP[\min(j + A _ i, h)], DP[j] + B _ i). \]
F - Silver Fox vs Monster
Solution
We can solve this problem by greedy method. We regard a bomb as a range attack on $[X, X + 2D + 1)$. Without loss of generalities, we can assume that $\{ (X _ i, H _ i) \}$ is in the ascending order. For each $i$, it is the best efficient to use bombs in $[X _ i, X _ i + 2D + 1)$ the minimum times we need to beat the monster $(X _ i, H _ i)$.
Here we have to compute the attack point on the current place $X _ i$ that we have made. This is controlled by cumulated sums and the manipulation of the queue. Every time we make the bomb attack on $X _ i$ in $cnt$ times, we possess the total damage in total += A * cnt; and the end of the range of the bomb by Q.emplace(X + 2 * D + 1, A * cnt);.
using Info = tuple<int, ll>;
queue<Info> Q;
ll ans{0};
ll total{0};
for (auto i = 0; i < N; ++i)
{
ll X, H;
tie(X, H) = V[i];
while (!Q.empty() && get<0>(Q.front()) <= X)
{
total -= get<1>(Q.front());
Q.pop();
}
ll cnt{max(0LL, (H - total + A - 1) / A)};
ans += cnt;
total += A * cnt;
Q.emplace(X + 2 * D + 1, A * cnt);
}