ABC181

https://atcoder.jp/contests/abc181

• Problem A

Takahashi wears white and black alternately, so the parity is the only concern here.

my submission

• Problem B

the sum of integers from A through B can be calculated as (A + B) * (B – A + 1) / 2. You just need to be careful at overflow.

my submission

• Problem C

You are given N points on a two dimensional coordinate plane. In order to check if a triple of distinct points is on the same line, It is enough to judge whether two vectors created from them are parallel to each other. Since we don’t want to use division here, the following equation will come in handy.

a * d = b * c ( if (a, b) || (c, d) )

You can solve this in O(N³).

my submission

• Problem D

A multiple of 8 can be made if the last three digits are a multiple of 8. So, count the number of each digit in the string at first. Then, search for how many digits there are in every multiple of 8. If there are enough to make a multiple of 8, you can output “Yes”. Note that when you get a string whose size is less or equal to 2, it will be better to deal with them other ways because they don’t have 3 digits in the first place.

my submission

• Problem E

let a < b < c < d. In this case,

{(d – a) + (c – d)} – {(b – a) + (d – c)} = 2c – 2b > 0

So, the equation {(d – a) + (c – d)} > {(b – a) + (d – c)} holds.

This means that it is the best way to place children and the teacher in the ascending order of height and make pairs from left.

Now, you need to know who is the best person to make a pair with the teacher. Since the constraints say that N ≦ 2 * 10⁵, you can brute force.

If you decide a person who is going to be a pair with the teacher, it is always optimum for the teacher to transform into the height which has the nearest height with that of the person. You can easily know this by binary search.

In order to calculate the sum of |x – y| faster, you need to use a prefix sum array.

Therefore you can solve this problem in O(NlogN).

my submission

• Problem F

For a circle of radius R to get to the right end, it needs to pass between two points or a point and a line. If a circle is tiny, the right end will be reachable. As the circle gets bigger, it will be more difficult for it to go through nails. So binary search would work here ( actually, you don’t need this).

Now, let us fix the radius R of a circle. if 2 * R > distance between nail A and nail B, it is impossible for it to pass between them. It might be easier to think that you draw a line between two nails if 2 * R > distance between nail A and nail B. Unless the path is completely blocked, there is always a path through which a circle can go. A path is completely blocked if the lines you have drawn connect the given two lines y = ±100.

So, let’s think about each nail and two lines as nodes and if 2 * R > distance between nail A and nail B, connect the corresponding nodes with an edge. Here, you consider two lines as nails but the distance between a line and a nail is the minimum possible one respectively.

If the nodes representing two lines are in one connected component, it would be impossible for a circle to get to the right end. Otherwise, it is possible.

So, we can use DSU and this problem can be solved by roughly O(N²logN).

But if you connect the nodes from small distance to large distance, you don’t have to use binary search because when you add a line between two nails and the path become completely blocked, it is the length you are looking for.

my submission