AtCoder Beginner Contest 143

Updated:

AtCoder Beginner Contest 143

Source codes

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.

Others