🧑💻
ABC375のC問題を理解したい
今回は，AtCoder Beginner Contest 375 C 問題を解いた際につまずいたポイントに関するメモを残しておきます．
C - Spiral Rotation
問題
入力例
8
.......#
.......#
.####..#
.####..#
.##....#
.##....#
.#######
.#######
出力例
........
#######.
#.....#.
#.###.#.
#.#...#.
#.#####.
#.......
########
操作によって，グリッドの各マスの色は以下のように変化（回転）します．
.......# ........ ........ ........ ........
.......# ######.. #######. #######. #######.
.####..# ######.. #....##. #.....#. #.....#.
.####..# → ##..##.. → #....##. → #.##..#. → #.###.#.
.##....# ##..##.. #..####. #.##..#. #.#...#.
.##....# ##...... #..####. #.#####. #.#####.
.####### ##...... #....... #....... #.......
.####### ######## ######## ######## ########
回答
N=int(input())
G=[input() for i in range(N)]
H=[[""]*N for i in range(N)]
for i in range(N):
for j in range(N):
ni,nj=i,j
d=min(i+1,j+1,N-i,N-j)
d %=4
while d>0:
ti,tj=nj,N-ni-1
ni,nj=ti,tj
d-=1
H[ni][nj]=G[i][j]
for i in range(N):
print("".join(H[i]))
解説
- 各マスの回転回数は、そのマスがグリッドの外側から何番目にあるかによって決まる
- min で求めた値を 4 で割った余りが実際の回転回数となる
- 回転は 90 度ずつ時計回りに行われる
入力の処理
N = int(input())
G = [input() for i in range(N)] # 元のグリッド
H = [[""]*N for i in range(N)] # 結果を格納するグリッド
マスごとの処理
for i in range(N):
for j in range(N):
回転回数の計算
d = min(i+1, j+1, N-i, N-j) # マスの外側からの距離を計算
d %= 4 # 4で割った余りが実際の回転回数
- 例えば、最も外側のマスは min(1, j+1, N-i, N-j) となる
- 2 番目の層は min(2, j+1, N-i, N-j) となる
- これにより、同じ層のマスは同じ回数回転する
回転の実行
ni, nj = i, j # 現在の位置
while d > 0:
ti, tj = nj, N-ni-1 # 90度時計回りの回転
ni, nj = ti, tj # 新しい位置を更新
d -= 1
-
90 度時計回りの回転は以下の変換：
- 新しい行 = 元の列
- 新しい列 = N - 元の行 - 1
結果の格納と出力
H[ni][nj] = G[i][j] # 回転後の位置に元の値を格納
for i in range(N):
print("".join(H[i])) # 結果の出力
計算量の分析：
- 空間計算量：O(N²)
- 時間計算量：O(N²)
- 各マスに対して最大 3 回の回転
- 下記のコードと比べて、各ステップでの深いコピーが不要
回転回数の計算
-
計算式: d = min(i+1, j+1, N-i, N-j)
これは各マスの「層の位置」を表しています。 -
具体例で N=8 の場合を視覚化してみると理解しやすいでしょう。
各マスの層の番号（min(i+1, j+1, N-i, N-j)の値）を表示してみます。
N=8 の場合の例で説明します。
- まず、各マスの層の位置（d = min(i+1, j+1, N-i, N-j)の値）を見てみましょう：
1 1 1 1 1 1 1 1 # 最外層
1 2 2 2 2 2 2 1
1 2 3 3 3 3 2 1
1 2 3 4 4 3 2 1
1 2 3 4 4 3 2 1
1 2 3 3 3 3 2 1
1 2 2 2 2 2 2 1
1 1 1 1 1 1 1 1 # 最外層
- この値を 4 で割った余り（d %= 4）が実際の回転回数になります：
1 1 1 1 1 1 1 1 # 余り1：1回回転
1 2 2 2 2 2 2 1 # 余り2：2回回転
1 2 3 3 3 3 2 1 # 余り3：3回回転
1 2 3 4 4 3 2 1 # 余り0：0回回転
1 2 3 4 4 3 2 1
1 2 3 3 3 3 2 1
1 2 2 2 2 2 2 1
1 1 1 1 1 1 1 1
- 回転回数が何を意味するのか：
- 最外層（値=1）：1 回の 90 度回転
- 2 番目の層（値=2）：2 回の 90 度回転（180 度）
- 3 番目の層（値=3）：3 回の 90 度回転（270 度）
- 4 番目の層（値=4）：4 回の 90 度回転（余り 0 なので回転なし）
- なぜこの計算方法が正しいのか：
- 各層は外側から内側に向かって、順番に:
- 1 回転（90 度）
- 2 回転（180 度）
- 3 回転（270 度）
- 0 回転（360 度=0 度）
という順番で回転していきます。
- min(i+1, j+1, N-i, N-j)の各項の意味：
- i+1: 上からの距離
- j+1: 左からの距離
- N-i: 下からの距離
- N-j: 右からの距離
この中の最小値を取ることで、そのマスが属する最も内側の層の番号が分かります。
例えば、座標(0,0)の場合：
- min(0+1, 0+1, 8-0, 8-0) = min(1, 1, 8, 8) = 1
つまり最外層（層 1）に属していることが分かります。
このように、各マスの位置に応じて適切な回転回数が自動的に計算され、結果として正しい回転パターンが得られます。
回転の実行
回転の実行部分をより理解しやすく書き換えることを考えてみましょう。
90 度時計回りの回転は、以下のような座標の変換になります：
- (i,j) → (j,N-1-i)
これを視覚的に理解しやすいように書き換えることができます。
まず、現在のコードを見てみましょう：
ni, nj = i, j # 初期位置
while d > 0:
ti, tj = nj, N-ni-1 # 90度時計回り回転
ni, nj = ti, tj # 新しい位置を更新
d -= 1
これを以下のように書き換えると、より理解しやすくなります：
方法 1: 回転の関数を定義する
def rotate_90_degrees(i, j, N):
"""座標(i,j)を90度時計回りに回転させる"""
return j, N-1-i
N = int(input())
G = [input() for i in range(N)]
H = [[""]*N for i in range(N)]
for i in range(N):
for j in range(N):
# 現在の位置
current_i, current_j = i, j
# マスの層を計算
layer = min(i+1, j+1, N-i, N-j)
rotations = layer % 4 # 必要な回転回数
# 指定回数だけ回転
for _ in range(rotations):
current_i, current_j = rotate_90_degrees(current_i, current_j, N)
# 最終位置に値を配置
H[current_i][current_j] = G[i][j]
# 結果の出力
for row in H:
print("".join(row))
方法 2: 回転回数ごとの座標を直接計算
N = int(input())
G = [input() for i in range(N)]
H = [[""]*N for i in range(N)]
for i in range(N):
for j in range(N):
# マスの層を計算
layer = min(i+1, j+1, N-i, N-j)
rotations = layer % 4 # 必要な回転回数
# 回転回数に応じて直接最終位置を計算
if rotations == 0: # 0度回転（そのまま）
new_i, new_j = i, j
elif rotations == 1: # 90度回転
new_i, new_j = j, N-1-i
elif rotations == 2: # 180度回転
new_i, new_j = N-1-i, N-1-j
else: # 270度回転
new_i, new_j = N-1-j, i
# 最終位置に値を配置
H[new_i][new_j] = G[i][j]
# 結果の出力
for row in H:
print("".join(row))
これらの改善点：
-
方法 1 の利点：
- 回転の処理が関数として分離され、コードの意図が明確
- 回転処理の再利用が容易
- デバッグが容易
-
方法 2 の利点：
- while ループが不要で、直接最終位置を計算
- 各回転パターンが明示的に書かれており、理解しやすい
- 実行速度が若干速い
-
両方の共通の改善点：
- 変数名がより説明的
- 処理の各ステップにコメントがある
- コードの構造が明確
回転の仕組みの説明：
90度回転の例（N=4の場合）：
(0,0) → (0,3)
(0,1) → (1,3)
(0,2) → (2,3)
(0,3) → (3,3)
一般化すると：
(i,j) → (j,N-1-i)
このように書き換えることで、コードの意図がより明確になり、メンテナンスも容易になります。また、デバッグ時にも各ステップでの座標の変化を追跡しやすくなります。
from copy import deepcopy
N = int(input())
A = []
for _ in range(N):
row = list(input().strip())
A.append(row)
for i in range(1, N // 2 + 1):
B = deepcopy(A)
for x in range(i - 1, N + 1 - i):
for y in range(i - 1, N + 1 - i):
# print(x, y)
B[y][N + 1 - x - 2] = A[x][y]
A = B
for row in B:
print(*row, sep="")
つまずいたところ
- 計算量が
O(N^2) - どのようにして計算量を減らすかがわからなかった．
- 記号が回転していることに気づけず，回転数を１，２，３のみを考慮すればよいことに気づけなかった．
- 4 回転は 0 回転と同じ，5 回転は 1 回転と同じ，6 回転は 2 回転と同じ，7 回転は 3 回転と同じ．
Discussion