AtCoder が提供しているABC（AtCoder Beginner Contest）375 C問題をC++とPythonで解いてみました。ABC375は、2024年10月12日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Spiral Rotation（Difficulty : 972）
問題の詳細は、リンク先をご覧ください。
先に回転したグリッドを4つ計算して、それを利用して最終結果を求めます。AtCoder Problems による Difficulty は 972 でした。
解答案
最初に定義通りに計算します。グリッド b を書き換えて、元のグリッド a に書き戻します（13ー21行目）。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<string> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n / 2; ++i) {
vector<string> b = a;
for (int x = i; x < n - i; ++x) {
for (int y = i; y < n - i; ++y) {
b[y][n - 1 - x] = a[x][y];
}
}
a = b;
}
for (int i = 0; i < n; ++i) {
cout << a[i] << endl;
}
return 0;
}残念ながら、このプログラムは、TLE（Time Limit Exceed）判定となります。
元のグリッド、90度回転、180度回転、270度回転したグリッドを先に計算しておきます。外周からの距離に基づいて、解のグリッドの値は以下となります。
- 一番外のグリッドは90度回転したグリッドとなります。
- その次の外のグリッドは180度回転したグリッドとなります。
- その次の外のグリッドは270度回転したグリッドとなります。
- その次の外のグリッドは元のグリッドとなります。
- その次の外のグリッドは90度回転したグリッドとなり、これ以降も繰り返しとなります。
C++ プログラム例（ABC375C）
上記の考え方をプログラムとして実装します。
- 90度回転したグリッドを b[0]、180度回転したグリッドを b[1]、270度回転したグリッド b[2]、元のグリッドを b[3] とします（18ー29行目）。
- 外からの距離を変数
indexとして計算します。その距離に従い、解のグリッドを埋めていきます（34、35行目）。
以下が、最終的なC++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<string> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
string space;
for (int i = 0; i < n; ++i) {
space += ' ';
}
vector<vector<string>> b(4, vector<string>(n, space));
for (int i = 0; i < 4; ++i) {
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (i == 0) {
b[i][y][n - 1 - x] = a[x][y];
} else {
b[i][y][n - 1 - x] = b[i - 1][x][y];
}
}
}
}
vector<string> result(n, space);
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
int index = min(min(x, n - 1 - x), min(y, n - 1 - y)) % 4;
result[x][y] = b[index][x][y];
}
}
for (int i = 0; i < n; ++i) {
cout << result[i] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC375C）
基本的な考え方は同じです。Python は文字列を書き換えることができないため、b と result をリストとして保持しています。
以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。
"""AtCoder Beginner Contest 375 C"""
n = int(input())
a = [input() for i in range(n)]
b = [[[" " for _ in range(n)] for _ in range(n)] for _ in range(4)]
for i in range(4):
for x in range(n):
for y in range(n):
if i == 0:
b[i][y][n - 1 - x] = a[x][y]
else:
b[i][y][n - 1 - x] = b[i - 1][x][y]
result = [[" " for _ in range(n)] for _ in range(n)]
for x in range(n):
for y in range(n):
index = min(x, n - 1 - x, y, n - 1 - y) % 4
result[x][y] = b[index][x][y]
for i in range(n):
print("".join(result[i]))最後に
一番最初に紹介した TLE 判定となったプログラムを提出した後、4つのグリッドを繰り返せば良いことに気付きました。残念ながら、コンテスト時間内にコーディングが間に合いませんでした。
引き続き ABC の問題を紹介していきます。
