ヒント → https://atcoder.jp/contests/agc066/editorial/9634

[1] 方針

\(k\) を定数として，

• \(i+j\) が偶数ならば \(A_{i,j}\equiv k\pmod{2d}\)
• \(i+j\) が奇数ならば \(A_{i,j}\equiv k+d\pmod{2d}\)

が成り立つようにすると，隣接する \(2\) マスの値の差が \(d\) 以上であるという目標を達成することができます．

この条件が成り立つようにするための最小コストを \(c_k\) としましょう．\(c_k\leq \frac{dN^2}{2}\) が成り立つような \(k\) が見つかれば本問題を解くことができます．

（ヒントで述べたように，\(A_{i,j}=0\) かつ \(d=1\) の場合などを考えると，\(i+j\) の偶奇によってそれぞれ何らかの性質が成り立つようにするというこの方針が思いつきやすいかもしれません．）

[2] \(c_k\leq \frac{dN^2}{2}\) となる \(k\) の存在証明

\(c_0 + c_d=dN^2\) が成り立つことを示しましょう．

そのためには各マスごとに，\(A_{i,j}\) を \(\pmod{2d}\) で \(0\) にするためのコスト \(c_{i,j,0}\) と，\(\pmod{2d}\) で \(d\) にするためのコスト \(c_{i,j,d}\) の総和が \(d\) であることを示せばよいです．

整数 \(n\) に対して \(A_{i,j} = n\cdot 2d + r\) （\(0\leq r < 2d\)）と書いたとき，

• \(0\leq r<d\) ならば，\(c_{i,j,0} = r\), \(c_{i,j,d}=d-r\)
• \(d\leq r<2d\) ならば，\(c_{i,j,0} =2d- r\), \(c_{i,j,d}=r-d\)

となるのでこれらの総和が \(d\) であることは容易に分かります．以上により \(c_0+c_d=dN^2\) が示された．

このことから \(c_0\) または \(c_d\) は \(\frac{dN^2}{2}\) 以下なので，\(c_k\leq \frac{dN^2}{2}\) となる \(k\) の存在が示されました．

なお，\(c_0 + \cdots + c_{2d-1}\) に注目して同様に証明することもできます．

上の証明を見れば分かるように，\(c_k\leq \frac{dN^2}{2}\) となる \(k\) は \(k=0, k=d\) の \(2\) 通りのどちらかとしてとることができ，これら \(2\) 通りを調べることで本問題は \(O(N^2)\) 時間で解くことができます．なお \(k=0, 1, \ldots, 2d-1\) のすべてを調べることでも \(O(dN^2)\) 時間で解くことができ，この方法でも十分 AC することが可能です．