AtCoder

ABC375 C問題(Spiral Rotation)を解く

AtCoder_ABC375_C

AtCoder が提供しているABC(AtCoder Beginner Contest)375 C問題をC++とPythonで解いてみました。ABC375は、2024年10月12日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Spiral Rotation(Difficulty : 972)

問題の詳細は、リンク先をご覧ください。

ABC375 C問題 Spiral Rotation

先に回転したグリッドを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 は文字列を書き換えることができないため、bresult をリストとして保持しています。

以下のプログラムは、「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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA