Forgot again?

Atcoder supports virtual contest now.

This is an "except for red" contest, so it's more like Div 1.5.

I think it is more difficult than Div1. I only solve 1 problem in the last contest...

Your cost is wrong.

Represent each robot as an interval [X-L, X+L], then use dp + binary search to find largest subset of intervals of intervals whose intersection is empty

Solved it just like the Interval Scheduling problem. Found the minimum number of intervals which are overlapping should be removed (using the standard greedy approach) and then the maximum robots we can keep is Total — minimum removed. https://www.geeksforgeeks.org/activity-selection-problem-greedy-algo-1/

Can you please explain D?

I find that even the data of keyence 2019 haven't been put into dropbox....

I think that B's coding difficulty is much higher than C. But I think these two problem's difficulty in thinking is almost the same. (Which one is more solvable depend on yourself.)

I also misunderstood "excluding the endpoints". During the contest, I think the movable range of arms of robot i is [xi − li + 1, xi + li − 1], not [xi − li, xi + li − 1]

Main ideas:

1. If two adjacent vertices $$$u$$$ and $$$v$$$ have $$$D_u = D_v$$$, it's possible to satisfy both by putting weight $$$D_u$$$ on the edge between them and giving the vertices opposite colors.
2. If two adjacent vertices $$$u$$$ and $$$v$$$ have $$$D_u \lt D_v$$$, it's possible to satisfy $$$v$$$ by putting weight $$$D_v - D_u$$$ on the edge between them and giving the vertices the same color.
3. If a vertex $$$v$$$ has no neighbor $$$u$$$ with $$$D_u \leq D_v$$$, it's not possible to satisfy $$$v$$$.

If no vertex violates (3), it's always possible to construct a valid coloring and weight assignment using (1) and (2). Implementation is straightforward if vertices are processed in non-decreasing order of $$$D$$$. Unused edges can be assigned a weight of $$$10^9$$$.

I sort by x-l,but implement strategy need some change.Sort by x+l I always see in some textbook. https://atcoder.jp/contests/keyence2020/submissions/9573530

We can reduce the problem to the following: Suppose that the board is initially uncolored. If exactly $$$i$$$ rows and $$$j$$$ columns are never chosen, then how many possible ways are there to color the grid? Either $$$i=j=0$$$ or $$$i,j \gt 0.$$$

A way to color the grid is valid if we can repeatedly remove rows or columns in which all of the squares are the same color until only uncolored squares are left. Call rows and columns that may be removed uniform. To count each such grid exactly once, we should specify an order in which uniform rows and columns should be removed.

• Step 1: Remove all uniform columns.
• Step 2: Remove all uniform rows.
• Step 3: Remove all uniform columns created by the removal of the rows in step 2.
• ... and so on.

Let $$$d$$$ be the number of distinct colors among the uniform rows or columns removed in the $$$i$$$-th step. It can be shown that $$$d$$$ is non-increasing over time (ignoring step 1). Furthermore, the number of ways to remove rows/columns on the $$$i+1$$$-st step depends only on $$$d$$$ after the $$$i$$$-th step and the number of rows/columns remaining.

For example, if only black rows were removed during step 2 ($$$d=1$$$), then no black columns can be removed during step 3, because they were already removed during step 1. This means that $$$d$$$ will still equal one for step 3 (unless no columns are removed at all). Note that when $$$x=y=0$$$, $$$d$$$ is equal to two after every step (again, ignoring step 1).

Code