B - Same Map in the RPG World Editorial by Nyaan
この問題は条件を満たす非負整数の組 \((s, t)\) が存在するかを判定する問題です。全ての非負整数の組に対して条件を満たすか判定していてはプログラムが終わらないので、まず \((s, t)\) として調べる必要のある組を絞り込みます。
すると、 \(s\) は \(0\) 以上 \(H\) 未満しか調べなくてよいことがわかります。なぜならば、\(A\) の高さは \(H\) なので全ての \(s\) について「 \(s\) 回縦方向シフトしたあとの \(A\) 」と「\(s + H\) 回縦方向シフトしたあとの \(A\) 」が一致するからです。
同様にして、\(t\) は \(0\) 以上 \(W\) 未満しか調べなくてよいことがわかります。よって調べる必要のある \((s, t)\) を \(HW\) 個に抑えることができました。
(以下の説明では \(A, B\) の添え字を 0-indexed で考えます。つまり、\(A\) の左上は \(A[0][0]\) で、右下は \(A[H-1][W-1]\) とします。)
\((s, t)\) を決め打ったときに、操作後の \(A\) と\(B\) が一致しているかを判定する問題を考えます。\(A\) を縦方向に \(s\) 回、横方向に \(t\) シフトすると \(A[i][j]\) は \(A[(i - s) \bmod H][(j - t) \bmod W]\) に移ります。(\(\bmod\) は余りを取る演算) よって、すべてのグリッドの地点 \((i, j)\) に対して \(A[(i - s) \bmod H][(j - t) \bmod W]\) と \(B[i][j]\) が一致するかを判定すればよいです。
このアルゴリズムは \(s, t, i, j\) の \(4\) 重ループになるので \(\mathrm{O}(H^2 W^2)\) の計算量で解けて、十分高速です。
- 実装例(C++)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
int H, W;
cin >> H >> W;
vector<string> A(H), B(H);
for (auto& x : A) cin >> x;
for (auto& x : B) cin >> x;
for (int s = 0; s < H; s++) {
for (int t = 0; t < W; t++) {
int ok = 1;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (A[(i - s + H) % H][(j - t + W) % W] != B[i][j]) ok = 0;
}
}
if (ok) {
cout << "Yes" << endl;
exit(0);
}
}
}
cout << "No" << endl;
}
posted:
last update: