AtCoder Beginner Contest 143

Updated:

AtCoder Beginner Contest 143

Source codesPermalink

SolutionsPermalink

A - CurtainPermalink

Flush max(0,A2B).

B - TAKOYAKI FESTIVAL 2019Permalink

Solution in O(N)-timePermalink

This problem can be solved in O(N)-time. Let S=iNAi,T=iNAi2. The answer is (S2T)/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 |xy|<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×103. 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(N2)-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,,N, let

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

We can compute f(x) by greedy algorithm. Let Hi={kNi=Ak}. Then, we can apply greedy algorithm. For iN, if Hix, we can use all elements whose value is i; otherwise, we can use up to x elements. Therefore, we have f(x)=1xiNmin(Hi,x). Here, we can speed up the calculation by defining Cj={i(N+1)Hij}. Then, we have f(x)=1xj(N+1)Cjmin(j,x)=1x(j=0xjCj+xj=x+1NCj). Here, we can use cumulated sum as follows. S[x]=j=0xjCj,T[x]=j=x+1NCj. We can calculate as follows. For S, let S[0]=0. Then, we execute, for xN, S[x+1]=S[x]+(x+1)Cx+1. For T, let T[0]=j=1NCj. Then, we execute, for xN, T[x+1]=T[x]Cx+1.

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

OthersPermalink