note: 初心者が典型パターンとして身につける方法としては、公式解説で触れられているものがおすすめです。あくまで別解としての紹介です。

マス \((i, j)\) について、まず「外周から何マス離れているか？」を考えます。これを \(k_{i, j}\) とおきます。

\(N=7\) を例にすると、次のようになります。

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 1 2 2 2 1 0
0 1 2 3 2 1 0
0 1 2 2 2 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0

これは、（実装のことを考えて \(i\), \(j\) を 0-indexed とすると）次のように計算できます。

\[ k_{i, j} = \min {\{i, j, N-i-1, N-j-1\}}. \]

また、外周からのマス数が共通のものたちを、それぞれ左上から時計回りに採番していくことを考えます。

 0  1  2  3  4  5  6
23  0  1  2  3  4  7
22 15  0  1  2  5  8
21 14  7  0  3  6  9
20 13  6  5  4  7 10
19 12 11 10  9  8 11
18 17 16 15 14 13 12

この番号についても、適切に場合分けなどをすることで、それぞれ \(O(1)\) 時間で計算できます。この番号を \(c_{i, j}\) とします。

さて、\(k_{i, j} < k\) (\(0 \le k < \frac N2\)) であるようなマスは \(N^2-(N-2k)^2\) 個なので、マス \((i, j)\) の番号は

\[ N^2-(N-2k_{i, j})^2 + c_{i, j} \]

と表せます。

提出 #49192379