AtCoder Beginner Contest 143
Updated:
Source codes
Solutions
A - Curtain
Flush $\max(0, A - 2B)$.
B - TAKOYAKI FESTIVAL 2019
Solution in $O(N)$-time
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
Solution
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;
This is just the run-length compression.
D - Triangles
Solution
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 or segment tree. Be careful that we have to exclude $x$ and $y$ and we have to divide the answer by $3$.
Caution
Be careful for overflow. The range of segment tree needs more than $2 \times 10^3$. The possibly maximum answer could be about $N ^ 3 \approx 8 \times 10 ^ 9.
Two-pointers
We can solve this problem by two-pointers. We sort $L$ in ascending order. We want to count the number of the triples $(j, i, x)$ with $j < i < x$ and $(L[j], L[i], L[x])$ makes a triangle. We fix $i$ and $j$. Then, by two-pointers of $(i, k)$ with $i < k < N$, we can find the answer in $O(N ^ 2)$-time.
sort(L.begin(), L.end());
ll ans{0};
for (auto i{1}; i < N - 1; ++i)
{
int k{i + 1};
for (auto j{0}; j < i; ++j)
{
while (k < N && L[k] < L[i] + L[j])
{
++k;
}
ans += k - i - 1;
}
}
cout << ans << endl;
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 speed up 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.