AtCoder が提供しているABC(AtCoder Beginner Contest)391 B問題をC++とPythonで解いてみました。ABC391は、2025年2月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Seek Grid(Difficulty : 110)
問題の詳細は、リンク先をご覧ください。
多重ループで全探索します。AtCoder Problems による Difficulty は 110 でした。
解答案
C++ プログラム例(ABC391B)
グリッドS左上の座標について2重ループ、グリッドTと一致しているかについて2重ループで全探索できます。ループ回数は多く見積もって
最後のループは文字列の一致を確認しているため(21行目)、見た目は3重ループになっています。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
vector<string> t(m);
for (int i = 0; i < m; ++i) {
cin >> t[i];
}
for (int i = 0; i <= n - m; ++i) {
for (int j = 0; j <= n - m; ++j) {
bool b = true;
for (int i2 = 0; i2 < m; ++i2) {
if (s[i + i2].substr(j, m) != t[i2]) {
b = false;
}
}
if (b) {
cout << i + 1 << " " << j + 1 << endl;
return 0;
}
}
}
return 0;
}
AC(Accepted=正しいプログラム)と判定されました。
Python プログラム例(ABC391B)
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 391 B"""
import sys
n, m = map(int, input().split())
s = [input() for _ in range(n)]
t = [input() for _ in range(m)]
result = 0
result = True
for i in range(n - m + 1):
for j in range(n - m + 1):
b = True
for i2 in range(m):
if s[i + i2][j:j + m] != t[i2]:
b = False
if b:
print(i + 1, j + 1)
sys.exit()
こちらも「AC」と判定されました。
最後に
なかなかレートが上がりませんが、ぼちぼちとプログラミングを楽しんでいます。
引き続き ABC の問題を紹介していきます。