D - Loong and Takahashi Editorial by rsk0315
別解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} \]
と表せます。
posted:
last update: