AtCoder が提供しているABC（AtCoder Beginner Contest）335 のD問題をC++とPythonで解いてみました。ABC335は、2024年1月6日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Loong and Takahashi（Difficulty : 431）
問題はリンク先をご覧ください。
ABC335 D問題 Loong and Takahashi
描くイメージが分かれば、後は実装の問題です。AtCoder Problems による Difficulty は 431 でした。
解答案
出力例1で、以下が提示されています。見やすくなるように空白を加えました。
1 2 3 4 5
16 17 18 19 6
15 24 T 20 7
14 23 22 21 8
13 12 11 10 9奇数×奇数のグリッドに対して、同じように左上から時計回りで数字を埋めていきます。
この問題の制約は、$3 \leqq N \leqq 45$ でした。$N = 45$ の場合、最後に埋められる数字は、$45 \times 45\; -\; 1 = 2024$ となります。
C++ プログラム例（ABC335D）
グリッドの移動（右下左上）量を配列 di と dj に格納しておきます。真ん中のグリッドには、0を設定します。出力時には、’T’ を出力します。
左上から右に範囲外（または既に数字が設定されている）になるまで、数字を設定していきます。次に下、左、上と数字を設定していきます。次は、また右に移動しながら数字を設定していきます。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<int>> a(n, vector<int>(n, -1));
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
a[n / 2][n / 2] = 0;
int num = 1;
int i = 0;
int j = 0;
a[j][i] = num;
int d = 0;
while (num < n * n - 1) {
int ni = i + di[d];
int nj = j + dj[d];
if ((0 <= ni)&&(ni < n)
&&(0 <= nj)&&(nj < n)
&&(a[nj][ni] == -1)) {
i = ni;
j = nj;
++num;
a[j][i] = num;
} else {
++d;
d %= 4;
}
}
for (int j = 0; j < n; ++j) {
for (int i = 0; i < n; ++i) {
if (i > 0) {
cout << " ";
}
if (a[j][i] == 0) {
cout << 'T';
} else {
cout << a[j][i];
}
}
cout << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC335D）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 335 D"""
n = int(input())
a = [[-1 for _ in range(n)] for _ in range(n)]
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
a[n // 2][n // 2] = 0
num = 1
i = 0
j = 0
a[j][i] = num
d = 0
while num < n * n - 1:
ni = i + di[d]
nj = j + dj[d]
if 0 <= ni < n and 0 <= nj < n and a[nj][ni] == -1:
i = ni
j = nj
num += 1
a[j][i] = num
else:
d += 1
d %= 4
for j in range(n):
for i in range(n):
if i > 0:
print(" ", end="")
if a[j][i] == 0:
print("T", end="")
else:
print(a[j][i], end="")
print()こちらも「AC」と判定されました。
最後に
正解のイメージができても、実装がやや重たい問題でした。
引き続き ABC の問題を紹介していきます。
