AtCoder Beginner Contest 153

Updated:

AtCoder Beginner Contest 153

• Review: 2020-06-16

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

$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);
}


Tags:

Categories: