【题解】AGC066A - Adjacent Difference

题目链接

https://atcoder.jp/contests/agc066/tasks/agc066_a

题目大意

给定一个 $N\times N$ 的方阵 $A_{i,j}$ 和一个正整数 $d$。每次可以花费 $x$ 的代价将矩阵的某一个位置加上 $x$ 或减去 $x$。请构造一种方案使得方阵中所有相邻位置的差的绝对值大于等于 $d$，且代价之和小于等于 $\frac{1}{2}{N}^{2}d$。

数据范围

• $2\le N\le 500$
• $1\le d\le 1000$
• $-1000\le A_{i,j}\le 1000$

解题思路

先说结论：

1. 将方阵黑白染色，然后将黑色的位置变为 $mod2d=0$ 的最近的数，将白色的位置变为 $mod2d=d$ 的最近的数，假设代价此为 $c_0$​。
2. 将方阵黑白染色，然后将白色的位置变为 $mod2d=0$ 的最近的数，将黑色的位置变为 $mod2d=d$ 的最近的数，假设代价此为 $c_1$。

则上述两种情况中必有一种满足条件。

证明：

由于上述构造中黑白相邻位置的差的绝对值至少为 $d$，所以满足第一个条件。

考虑第二个条件。假设把一个位置上的数变为 $mod2d=0$ 的最近数的代价为 $x$，变为 $mod2d=d$ 的最近的数的代价为 $y$，那么一定有 $x+y=d$。这就意味着 $c_0+c_1=N^{2}d$，则 $c_0$ 和 $c_1$ 中必有一个小于等于 $\frac{1}{2}{N}^{2}d$。

参考代码

https://atcoder.jp/contests/agc066/submissions/51989697