AtCoder Beginner Contest 143
Updated:
Source codesPermalink
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 S=∑i∈NAi,T=∑i∈NA2i. The answer is (S2−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 |x−y|<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=♯{k∈N∣i=Ak}. Then, we can apply greedy algorithm. For i∈N, if Hi≤x, we can use all elements whose value is i; otherwise, we can use up to x elements. Therefore, we have f(x)=1x∑i∈Nmin(Hi,x). Here, we can speed up the calculation by defining Cj=♯{i∈(N+1)∣Hi−j}. Then, we have f(x)=1x∑j∈(N+1)Cjmin(j,x)=1x(x∑j=0jCj+xN∑j=x+1Cj). Here, we can use cumulated sum as follows. S[x]=x∑j=0jCj,T[x]=N∑j=x+1Cj. We can calculate as follows. For S, let S[0]=0. Then, we execute, for x∈N, S[x+1]=S[x]+(x+1)Cx+1. For T, let T[0]=∑Nj=1Cj. Then, we execute, for x∈N, 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.