AtCoder

ABC391 B問題(Seek Grid)を解く

AtCoder_ABC391_B

AtCoder が提供しているABC(AtCoder Beginner Contest)391 B問題をC++とPythonで解いてみました。ABC391は、2025年2月1日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 Seek Grid(Difficulty : 110)

問題の詳細は、リンク先をご覧ください。

ABC391 B問題 Seek Grid

多重ループで全探索します。AtCoder Problems による Difficulty は 110 でした。

解答案

C++ プログラム例(ABC391B)

グリッドS左上の座標について2重ループ、グリッドTと一致しているかについて2重ループで全探索できます。ループ回数は多く見積もって 504=6.25×106 なので、計算も間にあいます。

最後のループは文字列の一致を確認しているため(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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA