AtCoder が提供しているABC（AtCoder Beginner Contest）300 のB問題をC++とPythonで解いてみました。ABC300は、2023年4月29日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Same Map in the RPG World（Difficulty : 353）
問題はリンク先をご覧ください。
ABC300 B問題 Same Map in the RPG World
与えられた文字のグリッドをシフトして条件を満たすか確認する問題です。AtCoder Problems による Difficulty は 353 でした。
解答案
$H$ と $W$ の上限が30となっています。縦と横のシフト量を決めて、グリッドが一致しているか確認する4重ループでも間に合います。計算量は、$O(H^2 \times W^2)$ となります。
C++ プログラム例（ABC300B）
縦のシフト量を sy で、横のシフト量を sx とします（18、19行目）。このシフト量に対して、シフトしたグリッドAとグリッドBが一致しているか確認します（21-27行目）。シフトした添え字は、H または W の剰余として計算しています（23行目）。
一致していた場合（変数 this_time が true）は、結果の変数 result を true にします（29行目）。最後に result に従い “Yes” か “No” を出力します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w;
cin >> h >> w;
vector<string> a(h);
for (int i = 0; i < h; ++i) {
cin >> a[i];
}
vector<string> b(h);
for (int i = 0; i < h; ++i) {
cin >> b[i];
}
bool result = false;
for (int sy = 0; sy < h; ++sy) {
for (int sx = 0; sx < w; ++sx) {
bool this_time = true;
for (int y = 0; y < h; ++y) {
for (int x = 0; x < w; ++x) {
if (a[(y - sy + h)% h][(x - sx + w)% w] != b[y][x]) {
this_time = false;
}
}
}
if (this_time) {
result = true;
}
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC300B）
C++のロジックをそのまま Python に書き直しました。Python は、インデントで条件文やループ文の範囲を示すため、4重ループも見やすくなっています。
"""AtCoder Beginner Contest 300 B"""
h, w = map(int, input().split())
a = [input() for i in range(h)]
b = [input() for i in range(h)]
result = False
for sy in range(h):
for sx in range(w):
this_time = True
for y in range(h):
for x in range(w):
if a[(y - sy + h) % h][(x - sx + w) % w] != b[y][x]:
this_time = False
if this_time:
result = True
print("Yes" if result else "No")こちらも「AC」と判定されました。
最後に
入力例4で、以下の文字列が入力として与えられました。「ABC」と読めます。
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................$(s, t) = (9, 14) で変換すると以下になります。「300!」と読めます。
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...工夫して楽しい例を示していただきました。
引き続き ABC の問題を紹介していきます。
