AtCoder Beginner Contest 143
Updated:
Source codesPermalink
SolutionsPermalink
A - CurtainPermalink
Flush .
B - TAKOYAKI FESTIVAL 2019Permalink
Solution in -timePermalink
This problem can be solved in -time. Let The answer is .
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 and . The candidate of is such that We can count such by cumulated sum or segment tree. Be careful that we have to exclude and and we have to divide the answer by .
CautionPermalink
Be careful for overflow. The range of segment tree needs more than . 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 in ascending order. We want to count the number of the triples with and makes a triangle. We fix and . Then, by two-pointers of with , we can find the answer in -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.
how many tanks we need to travel from to .
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 where we can travel from to by one tank, i.e., the distance between and is less than or equal to .
the distance between and .
This can also be generated by Warshall-Floyd’s algorithm.
F - Distinct NumbersPermalink
Assume -indexed.
SolutionPermalink
First, we “swap” the answer and the input. For , let
the maximum of so that we can divide the into disjoint subsets where each of them includes elements.
We can compute by greedy algorithm. Let Then, we can apply greedy algorithm. For , if , we can use all elements whose value is ; otherwise, we can use up to elements. Therefore, we have Here, we can speed up the calculation by defining Then, we have Here, we can use cumulated sum as follows. We can calculate as follows. For , let . Then, we execute, for , For , let . Then, we execute, for ,
Returning back to the original problem, we can see that the greater is, the less valued is. For , the answer is the maximum of so that . This is determined by Meguru’s binary search.