AtCoder Beginner Contest 143

Source codesPermalink

• My submissions (AtCoder)
• My source codes (GitHub)

SolutionsPermalink

A - CurtainPermalink

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

B - TAKOYAKI FESTIVAL 2019Permalink

Solution in $O(N)$-timePermalink

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 - SlimesPermalink

SolutionPermalink

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 - TrianglesPermalink

SolutionPermalink

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

CautionPermalink

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-pointersPermalink

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 CarPermalink

SolutionPermalink

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 NumbersPermalink

Assume $0$-indexed.

SolutionPermalink

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.

OthersPermalink