QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: Anonymous

Posted at: 2026-04-22 17:04:42

Last updated: 2026-04-22 17:05:02

Back to Problem

Official Editorial

We can identify a key strategy: if player A leads player B by a sufficiently large margin, A can make three consecutive moves of distance $1$ to occupy four consecutive positions. This effectively blocks B from reaching any position beyond A's current location.

Specifically, suppose it is the leading player A's turn, with A at position $u$ and B at position $v$, where $u - v \geqslant 6$. In this case, A can force a block on B using a state sequence like the following (taking $v = u-6$ as an example): $(u-6,u) \to (u-6,u+1) \to (u-2,u+1) \to (u-2,u+2) \to (u-1,u+2) \to (u-1,u+3)$.

This constitutes the optimal strategy for both sides. Player A can guarantee that the final score difference is at most the value achieved in this scenario, because once B is blocked, A is guaranteed to claim all remaining positions in the suffix. Conversely, player B can guarantee that the score difference is at least this value, since regardless of how A plays, B can secure all positions in this intermediate segment.

Consequently, we can solve the problem using a backward DP. The state needs to track the position of the leading player, the distance gap $\in [0,5]$ between them, and a $2^4$ bitmask to record the occupancy status of the positions between the two players. This yields an $O(n)$ time complexity, and space complexity is easily manageable using rolling array optimization.

During implementation, note that after making a move, the leading player might temporarily extend their lead to a distance of $\geqslant 6$. However, on the subsequent turn, they will either move back to reduce the gap, or the situation will naturally fall into the blocking case described above.

Comments

No comments yet.