Hints: https://atcoder.jp/contests/agc066/editorial/9708

[1] Strategy

Let \(k\) be a constant. If the following conditions are satisfied, we can achieve the goal that the difference in values between any two adjacent cells is at least \(d\):

• if \(i+j\) is even, \(A_{i,j}\equiv k\pmod{2d}\);
• if \(i+j\) is odd, \(A_{i,j}\equiv k+d\pmod{2d}\).

Let \(c_k\) denote the minimum cost to satisfy these conditions. If we can find a \(k\) such that \(c_k\leq \frac{dN^2}{2}\), we can solve this problem.

(As mentioned in the hints, considering cases such as \(A_{i,j}=0\) and \(d=1\) might make it easier to develop this strategy of making some property hold based on the parity of \(i+j\).)

[2] Proof of the existence of \(k\) such that \(c_k\leq \frac{dN^2}{2}\)

Let us show that \(c_0 + c_d=dN^2\) holds.

To do so, it is enough to show for each cell that the cost \(c_{i,j,0}\) of converting \(A_{i,j}\) to \(0\) modulo \(2d\) and the cost \(c_{i,j,d}\) of converting it to \(d\) modulo \(2d\) sums up to \(d\).

When we write \(A_{i,j} = n\cdot 2d + r\) (\(0\leq r < 2d\)) for an integer \(n\),

• if \(0\leq r<d\), then \(c_{i,j,0} = r\) and \(c_{i,j,d}=d-r\);
• if \(d\leq r<2d\), then \(c_{i,j,0} =2d- r\) and \(c_{i,j,d}=r-d\).

It is easy to see that the sum of these is \(d\). Thus, it has been shown that \(c_0+c_d=dN^2\).

From this, either \(c_0\) or \(c_d\) is less than or equal to \(\frac{dN^2}{2}\), proving the existence of \(k\) such that \(c_k\leq \frac{dN^2}{2}\).

You can also prove this by focusing on \(c_0 + \cdots + c_{2d-1}\) in a similar manner.

As can be seen from the proof above, \(k\) can be taken as \(k=0\) or \(k=d\), and examining these two cases solves this problem in \(O(N^2)\) time. Alternatively, examining all \(k=0, 1, \ldots, 2d-1\) solves it in \(O(dN^2)\) time, which is also sufficient for getting accepted.