\(5\times 5\) の正方形 \(C\) であって、 \(C_{1,1} \neq C_{5,1}\) を満たすものについて考察します。

ここで、左上を \((p,q)\) 、右下を \((r,s)\) とする部分長方形を \((p,q)\to (r,s)\) と表現します。

\(C_{1,1}\ C_{1,2}\ C_{1,3}\ C_{1,4}\ C_{1,5}\\ C_{2,1}\ C_{2,2}\ C_{2,3}\ C_{2,4}\ C_{2,5}\\ C_{3,1}\ C_{3,2}\ C_{3,3}\ C_{3,4}\ C_{3,5}\\ C_{4,1}\ C_{4,2}\ C_{4,3}\ C_{4,4}\ C_{4,5}\\ C_{5,1}\ C_{5,2}\ C_{5,3}\ C_{5,4}\ C_{5,5}\\\)

このとき、 \(C_{1,1}\) 以外の左上 \(4\times 4\) に \(C_{1,1}\) が含まれないことより、 \((2,1)\to (4,4)\) には \(C_{1,1}\) と等しい値は含まれません。 \(C_{1,1} \neq C_{5,1}\) と左下の条件より、 \(C_{5,2},C_{5,3},C_{5,4}\) のうちいずれかが \(C_{1,1}\) と等しいです。ここで右下の条件より、 \((2,2)\to (4,5)\) には \(C_{1,1}\) と等しい値は含まれません。左上の条件より \((1,2)\to (4,4)\) にも \(C_{1,1}\) と等しい値は含まれませんから、結局 \(C_{1,1} = C_{1,5}\) が成り立ちます。

ここで、すべての \(0 \le t,u < 4\) について、以下の少なくともどちらかが成り立ちます。

• すべての \(i\) について、 \(A_{4i+t,u}=A_{4i+t,4+u}=A_{4i+t,8+u}=\ldots\)
• すべての \(j\) について、 \(A_{t,4j+u}=A_{4+t,4j+u}=A_{8+t,4j+u}=\ldots\)

これを証明しましょう。

\(\bmod 4\) ごとに取り出して、 \(D_{i,j} \neq D_{i,j+1}\) ならば \(D_{i-1,j}=D_{i,j}=D_{i+1,j},D_{i-1,j+1}=D_{i,j+1}=D_{i+1,j+1}\) 、\(i\) と \(j\) が逆でも同様の条件を満たす数列 \(D\) を考えます。すると、

• ある \((i,j)\) が存在して、 \(D_{i,j} \neq D_{i,j+1}\)
• ある \((i,j)\) が存在して、 \(D_{i,j} \neq D_{i+1,j}\)

を同時に満たすことが不可能であることを示せばよく、また \(D_{i,j}\neq D_{i,j+1}\) ならば \(D_{*,j},D_{*,j+1}\) がそれぞれすべて同じ値になることは、条件を繰り返し適用することで示せます。

これを適用すると、明らかに矛盾が生じることがわかります。よって示せました。

また、すべての \(1 \le k \le 16\) に対し、以下のいずれかが成り立ちます。

• ある \((t,u)\) が存在し、すべての \((i,j)\) に対し \(A_{4i+t,4j+u}=k\) かつそれ以外に \(k\) となる場所は存在しない

• ある \(t\) が存在し、すべての \(i\) に対してある \(u\) が存在して、すべての \(j\) に対し \(A_{4i+t,4j+u}=k\) かつそれ以外に \(k\) となる場所は存在しない

• ある \(u\) が存在し、すべての \(j\) に対してある \(t\) が存在して、すべての \(i\) に対し \(A_{4i+t,4j+u}=k\) かつそれ以外に \(k\) となる場所は存在しない

まどろっこしいですが、すなわちすべての値について、縦方向または横方向にしか存在しない、ということを述べています。証明は単純で、縦と横に交差するとしたとき、異なる \((i \bmod 4,j \bmod 4)\) ならば条件に矛盾し、等しい \((i \bmod 4,j \bmod 4)\) ならばそれだけで盤面を埋め尽くすことが述べられ、また縦のみで構成することを考えると等間隔に置いていくしかないことから証明できます。

\((i\bmod 4,j \bmod 4)\) は高々 \(16\) 個しかないので、それについて縦または横を決め打つことを考えます。同じ行で異なる \(\bmod 4\) に同じ値がある場合、同じ行の等しい \(\bmod 4\) に異なる \(\bmod 4\) がある場合などのあり得ない場合を取り除くと、あとは簡単な条件で書けます。計算量は \(K=4\) として \(O(N^2K^2 + 2^{K^2} poly(K))\) です。

想定解

余談 : 考察を推し進めると、最終的に問題が長さ \(K(=4)\) の数列 \(X,Y\) と \(K\times K\)行列 \(A(-1 \le A_{i,j})\) が与えられて、 \((i,j)\) ごとに以下のどちらかを行う :

• \(X_i\) から \(A_{i,j}\) を引く
• \(Y_j\) から \(A_{i,j}\) を引く

最終的に \(0 \le X_i,Y_j\) を満たすようにできるか？

という問題になります。これを考察するともう少し高速に解ける可能性があります。