Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 300 B問題 Same Map in the RPG World

AtCoder ABC ABC300 B問題 200 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$H$ 行 $W$ 列の ${\tt .}, {\tt \#}$ からなる行列 $A,B$ が与えられる.

ここで, 縦方向のシフトと横方向のシフトを次のように定義する.

縦方向のシフト: $A$ の $1$ 行目を $H$ 行目に移動させる.
横方向のシフト: $A$ の $1$ 列目を $W$ 列目に移動させる.

次を満たす非負整数の組 $(s,t)$ は存在するか?

$A$ に対して, 縦方向のシフトを $s$ 回, 横方向のシフトを $t$ 回行うと, $A,B$ は一致する.

制約

$2 \leq H,W \leq 30$
$A,B$ の各要素は ${\tt \#}, {\tt .}$ からなる.

解法

縦方向のシフトを続けて $s$ 回行った後の行列と, 縦方向のシフトを続けて $(s+H)$ 回行った後の行列は一致する. よって, $0 \leq s \lt H$ の場合について考えれば良い.

横方向についても同様にして, $0 \leq t \lt W$ とてもよい.

すると, 各 $s,t$ に対して, $A=B$ となるかどうかは $O(HW)$ 時間で判定できる.

よって, 全体で $O(H^2 W^2)$ 時間で判定できる.