# AtCoder Beginner Contest 143

Updated:

AtCoder Beginner Contest 143

# Solutions

## A - Curtain

Flush $\max(0, A - 2B)$.

## B - TAKOYAKI FESTIVAL 2019

This problem can be solved in $O(N)$-time. Let \begin{align} S &= \sum _ {i \in N} A _ i, \\\ T &= \sum _ {i \in N} A _ i ^ 2. \end{align} The answer is $(S ^ 2 - T) / 2$.

## C - Slimes

Execute the following code.

  int ans{0};
char x{'D'};
for (auto i = 0; i < N; ++i)
{
if (x != S[i])
{
++ans;
x = S[i];
}
}
cout << ans << endl;


## D - Triangles

Try all $x$ and $y$. The candidate of $z$ is such that $\lvert x - y \rvert < z < x + y.$ We can count such $z$ by cumulated sum. Be careful that we have to exclude $x$ and $y$ and we have to divide the answer by $3$.

## E - Travel by Car

### Solution

Suppose that we have the grid such as the following.

$E[i][j] =$ how many tanks we need to travel from $i$ to $j$.

If we have this grid, we are immediately done. But this grid can be generated by Warshall–Floyd’s algorithm. The seeds of it that $E[i][j] = 1$ where we can travel from $i$ to $j$ by one tank, i.e., the distance between $i$ and $j$ is less than or equal to $L$.

$D[i][j] =$ the distance between $i$ and $j$.

This can also be generated by Warshall–Floyd’s algorithm.

## F - Distinct Numbers

Assume $0$-indexed.

### Solution

First, we “swap” the answer and the input. For $x = 1, \dots, N$, let

$f(x) =$ the maximum of $y$ so that we can divide the $\{ A _ i \}$ into $x$ disjoint subsets where each of them includes $y$ elements.

We can compute $f(x)$ by greedy algorithm. Let $H _ i = \sharp \{ k \in N \mid i = A _ k \}.$ Then, we can apply greedy algorithm. For $i \in N$, if $H _ i \leq x$, we can use all elements whose value is $i$; otherwise, we can use up to $x$ elements. Therefore, we have $f(x) = \frac{1}{x} \sum _ {i \in N} \min(H _ i, x).$ Here, we can fasten the calculation by defining $C _ j = \sharp \{ i \in (N + 1) \mid H _ i - j \}.$ Then, we have $f(x) = \frac{1}{x} \sum _ {j \in (N + 1)} C _ j \min(j, x) = \frac{1}{x} \left( \sum _ {j = 0} ^ x j C _ j + x \sum _ {j = x + 1} ^ N C _ j \right).$ Here, we can use cumulated sum as follows. \begin{align} S[x] &= \sum _ {j = 0} ^ x j C _ j, \\\ T[x] &= \sum _ {j = x + 1} ^ N C _ j. \end{align} We can calculate as follows. For $S$, let $S[0] = 0$. Then, we execute, for $x \in N$, $S[x + 1] = S[x] + (x + 1) C _ {x + 1}.$ For $T$, let $T[0] = \sum _ {j = 1} ^ N C _ j$. Then, we execute, for $x \in N$, $T[x + 1] = T[x] - C _ {x + 1}.$

Returning back to the original problem, we can see that the greater $x$ is, the less valued $f(x)$ is. For $k = 1, \dots, N$, the answer is the maximum of $x$ so that $f(x) \geq k$. This is determined by Meguru’s binary search.

Tags:

Categories: