If I was tired from the noon event, I completely forgot to attend.
C
- Thoughts.
- N is 100, so there is room for a square order.
- Find the vector connecting each pair, which can be afforded
- But if you naively do the “are there two vectors with the same orientation?” thing, it’s 10^8, which is suspicious.
- There’s a feeling that if we cut it in half, we could make it in time.
- If not, put the irreducible fraction in the SET.
- At this time, you can put the opposite-facing ones together.
- Official Explanation
- Triple loop is good if the decision is constant.
- Match determination of slope can eliminate divisors.
D
- Thoughts.
- The length of S is quite long, but you can tell if it is a multiple of 8 by looking at the remainder divided by 1000, so the point is just 3 letters
- Find the frequency of occurrence of each number in the order of the length of S
- We can mechanically enumerate 125 different “conditions that are multiples of 8” and check whether a given number satisfies them
- Official Explanation OK
ABC181E F
- Thoughts.
- It’s hard to describe the area.
- Once a region is represented, the distance of a point is used to determine how much less than or equal to its diameter it must be to move from one region to another.
- I wonder if it divides into triangles, Voronoi division.
- What is needed is not the Voronoi partition itself, but the pair of which point and which point to choose when doing the Voronoi partition
- Is it more mainstream to call it the “Delaunay split” or the “Delaunay split?
- After doing that, from the end vertex, you need to check if you can extend it without intersecting other edges up or down, and you need to carve the outer passage as well.
- Assuming we get that far, this is not the maximum flow, so we have to figure out how to solve it.
- N is 100 at best, area is about 200 at worst.
- Once the radius is determined, each side becomes “passable passable”. Whether the start and goal are connected or not can be determined by DFS, fast enough.
- Maximum radius is 100 and required accuracy is 10^-4
- A bifurcated search can be narrowed down to about 20 times.
- Official Explanation
- Focus on walls, not areas
- Impassable if the upper and lower walls are connected by a wall.
- Just look at the distance between two points to see if it is a wall.
- Sort the distances and increase from the smallest to the largest until they become consolidated.
This page is auto-translated from /nishio/ABC181 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.