五条悟与矩阵游戏题解

思路

若一名玩家被迫走到分值低于上一步的格子，对手下一步可以回到刚才的高分格。经过极多轮后，先取得高分的一方会领先。因此最优游戏等价于：每一步都必须走到距离大于 $k$ 且分值更高的格子，无法继续的一方失败。

按分值从大到小处理格子。设 win(x,y) 表示刚刚在该格落子的玩家最终获胜。对手会从所有距离大于 $k$ 的更高分格子中选择，所以当前格是胜态，当且仅当所有可达的更高分胜态都不存在；等价地，所有已经处理出的胜态都与当前格距离不超过 $k$。

小规模可以不记忆地递归枚举全部后续策略。中规模按分值递减做动态规划，并显式扫描所有已有胜态，复杂度为 $O(n^4)$。

做法

利用恒等式

$$|x-x'|+|y-y'|=\max\bigl(|(x+y)-(x'+y')|, |(x-y)-(x'-y')|\bigr).$$

维护所有已出现胜态的四个极值：

$$\min(x+y),\ \max(x+y),\ \min(x-y),\ \max(x-y).$$

一个新格子 $(x,y)$ 与所有胜态的曼哈顿距离都不超过 $k$，当且仅当它的 $x+y$ 与 $x-y$ 到对应两个端点的距离均不超过 $k$。若条件成立，就把该格标为 M 并更新四个极值；否则标为 G。

最大分值格没有更高后继，必为胜态。由于分值互异，可以直接用分值到坐标的映射按 $n^2,n^2-1,\ldots,1$ 处理，从而省去排序。题目允许输出 D，但在分值互异且双方最优的条件下不会出现平局。

复杂度

使用分值到坐标映射时，时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$；使用排序的独立满分实现为 $O(n^2\log n)$。