\(m_{i,j}\) は \(S\) の要素の総和に \(2N-1\) 回寄与するため、スコアの最大値が \(N^2\) であるための必要条件は \(X\) の総和が \(2N-1\) の倍数であることです。また、これは十分条件でもあります。まず、この場合の構成法を示します。

各 \(i,j\) に対し、\(i\) 行 \(j\) 列目に対する総和を \(s_{i,j}\) とする方法を考えます。\(s_{i,j}\) の総和を \(\mathrm{sum}\)、\(i\) 行目に対する \(s_{i,j}\) の総和を \(r_i\)、\(j\) 列目に対する \(s_{i,j}\) の総和を \(c_j\) とした時、\(m_{i,j} = -2 \mathrm{sum} + (2N-1)(r_i+c_j) - (2N-1)(N-1)s_{i,j} \) とすると \(i\) 行 \(j\) 列目に対する総和が \((2N-1)(N-1)s_{i,j}\) となります。このため、この式の値が \(2N-1\) の倍数かつ \(N-1\) の倍数の時( \(2N-1\) と \(N-1\) は互いに素なのでこの条件は独立に扱えます)、\((2N-1)(N-1)\) で割ることで目的が達成できます。
現在は \(X\)の要素の総和 が \(2N-1\) の倍数の場合を考えているため、 \(2N-1\) の倍数という条件は満たされています。
問題は \(N-1\) の倍数という条件で、これは一般に満たされないため、\(X\) の要素と \(s_{i,j}\) を適切に対応させる必要があります。\(r_1,\ldots,r_N,c_1,\ldots,c_N\) が \(\mathrm{mod}\) \(N-1\) で等しくなるようにすると上の式は \(N-1\) の倍数となるため、そのように \(s_{i,j}\) を定めることにします。

以降、添え字を 0-indexed とし、 \([0,N)\) に収まらない場合、\(\mathrm{mod}\) \(N\) で等しいものを考えることにします。

\(N\) が奇数の場合、\(s_{i,j} = a_{-i+j} + b_{-2i+j}\) とすると、どの行・列も総和が \(\sum a_i + \sum b_i\) となり、条件を満たします。

\(N\) が偶数の場合、同様に \(s_{i,j} = a_k + b_l\) と表します。まず \(a_0,a_{\frac{N}{2}}\) が \(\mathrm{mod}\) \(N-1\) で等しくなるように並び替えます。そして、\(k\) を次のように定めます。

\[ k = \begin{cases} -i+j & (-i+j \neq 0 かつ -i+j \neq \frac{N}{2}) \\ \frac{N \times( i \bmod 2)}{2} & (-i+j = 0 または -i+j = \frac{N}{2}) \end{cases} \]

\(l=1,2,\ldots,N\) に対しては、\(l\) と対応する \((i,j)\) を次のように定めます。

• \(x=0,1,\ldots,\frac{N}{2}-1\) に対する \((2 \lfloor \frac{l}{2}\rfloor + \frac{N \times( l \bmod 2)}{2} + x, 2 \lfloor \frac{l}{2}\rfloor+2x)\)
• \(x=\frac{N}{2}, \frac{N}{2}+1,\ldots,N-1\) に対する \((2 \lfloor \frac{l}{2}\rfloor + \frac{N \times( l \bmod 2)}{2} + x, 2 \lfloor \frac{l}{2}\rfloor+2x+1)\)

すると、条件を満たします。

以上を基に構成することで \(X\) の総和が \(2N-1\) の倍数の場合はスコアの最大値 \(N^2\) を達成することが出来ました。

\(X\) の総和が \(2N-1\) の倍数でない場合、上述の方法で \(\mathrm{mod}\) \(N-1\) が合うように \(s_{i,j}\) を合わせた後、適当な \(s_{i,j}\) を \(+N-1\) し続けることで( \(N-1\) と \(2N-1\) は互いに素なので) \(N-1\) の倍数という条件を保ったまま総和を \(2N-1\) の倍数に出来、最大値 \(N^2-1\) を達成できます。