AtCoder が提供しているABC（AtCoder Beginner Contest）302 のB問題をC++とPythonで解いてみました。ABC302は、2023年5月20日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Find snuke（Difficulty : 352）
問題はリンク先をご覧ください。
グリッドに存在する特定の文字列を探す問題です。AtCoder Problems による Difficulty は 352 でした。
解答案
グリッドの問題は、縦方向と横方向の差分を配列として格納しておくとすっきりと書けます。ABC269 D問題でも使った手法です。
C++ プログラム例（ABC302B）
8方向の横方向と縦方向の差分を配列 dx と dy として格納しておきます（13、14行目）。探す文字数（”snuke” の5文字）を8方向に伸ばしても与えられたグリッドの範囲に入っていることを確認します（19-24行目）。そのあとで、一時変数 t に格納して “snuke” と比較します（26-29行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w;
cin >> h >> w;
vector<string> s(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
for (int k = 0; k < 8; ++k) {
if ((dx[k] * 4 + j < 0)||(w <= dx[k] * 4 + j)) {
continue;
}
if ((dy[k] * 4 + i < 0)||(h <= dy[k] * 4 + i)) {
continue;
}
string t = "";
for (int m = 0; m < 5; ++m) {
t += s[dy[k] * m + i][dx[k] * m + j];
}
if (t == "snuke") {
for (int m = 0; m < 5; ++m) {
cout << dy[k] * m + i + 1 << " " << dx[k] * m + j + 1 << endl;
}
}
}
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC302B）
Python 版は C++ 版をそのまま移植しました。
"""AtCoder Beginner Contest 302 B"""
h, w = map(int, input().split())
s = [input() for i in range(h)]
dx = [1, -1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
for i in range(h):
for j in range(w):
for k in range(8):
if dx[k] * 4 + j < 0 or w <= dx[k] * 4 + j:
continue
if dy[k] * 4 + i < 0 or h <= dy[k] * 4 + i:
continue
t = ""
for m in range(5):
t += s[dy[k] * m + i][dx[k] * m + j]
if t == "snuke":
for m in range(5):
print(dy[k] * m + i + 1, dx[k] * m + j + 1)こちらも「AC」と判定されました。
最後に
コンテストに提出したプログラムは、この記事の最後に紹介します。当初、4方向だけ探索していました。それで足りないことが分かり、8方向を探索するように書き換えて提出しました。これは一度でAC判定となりましたが、非常に煩雑です。多くの添え字を正確に書く必要があります。
このため、グリッドでよく使われるプログラムに書き換えて紹介しました。
引き続き ABC の問題を紹介していきます。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w;
cin >> h >> w;
vector<string> s(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (j + 4 < w) {
// 左→右
if ((s[i][j + 0] == 's')
&&(s[i][j + 1] == 'n')
&&(s[i][j + 2] == 'u')
&&(s[i][j + 3] == 'k')
&&(s[i][j + 4] == 'e')) {
cout << i + 1 << " " << j + 0 + 1 << endl;
cout << i + 1 << " " << j + 1 + 1 << endl;
cout << i + 1 << " " << j + 2 + 1 << endl;
cout << i + 1 << " " << j + 3 + 1 << endl;
cout << i + 1 << " " << j + 4 + 1 << endl;
return 0;
}
// 右→左
if ((s[i][j + 4] == 's')
&&(s[i][j + 3] == 'n')
&&(s[i][j + 2] == 'u')
&&(s[i][j + 1] == 'k')
&&(s[i][j + 0] == 'e')) {
cout << i + 1 << " " << j + 4 + 1 << endl;
cout << i + 1 << " " << j + 3 + 1 << endl;
cout << i + 1 << " " << j + 2 + 1 << endl;
cout << i + 1 << " " << j + 1 + 1 << endl;
cout << i + 1 << " " << j + 0 + 1 << endl;
return 0;
}
}
if (i + 4 < h) {
// 上→下
if ((s[i + 0][j] == 's')
&&(s[i + 1][j] == 'n')
&&(s[i + 2][j] == 'u')
&&(s[i + 3][j] == 'k')
&&(s[i + 4][j] == 'e')) {
cout << i + 0 + 1 << " " << j + 1 << endl;
cout << i + 1 + 1 << " " << j + 1 << endl;
cout << i + 2 + 1 << " " << j + 1 << endl;
cout << i + 3 + 1 << " " << j + 1 << endl;
cout << i + 4 + 1 << " " << j + 1 << endl;
return 0;
}
// 下→上
if ((s[i + 4][j] == 's')
&&(s[i + 3][j] == 'n')
&&(s[i + 2][j] == 'u')
&&(s[i + 1][j] == 'k')
&&(s[i + 0][j] == 'e')) {
cout << i + 4 + 1 << " " << j + 1 << endl;
cout << i + 3 + 1 << " " << j + 1 << endl;
cout << i + 2 + 1 << " " << j + 1 << endl;
cout << i + 1 + 1 << " " << j + 1 << endl;
cout << i + 0 + 1 << " " << j + 1 << endl;
return 0;
}
}
if ((j + 4 < w)&&(i + 4 < h)) {
// 左上→右下
if ((s[i + 0][j + 0] == 's')
&&(s[i + 1][j + 1] == 'n')
&&(s[i + 2][j + 2] == 'u')
&&(s[i + 3][j + 3] == 'k')
&&(s[i + 4][j + 4] == 'e')) {
cout << i + 0 + 1 << " " << j + 0 + 1 << endl;
cout << i + 1 + 1 << " " << j + 1 + 1 << endl;
cout << i + 2 + 1 << " " << j + 2 + 1 << endl;
cout << i + 3 + 1 << " " << j + 3 + 1 << endl;
cout << i + 4 + 1 << " " << j + 4 + 1 << endl;
return 0;
}
// 右下→左上
if ((s[i + 4][j + 4] == 's')
&&(s[i + 3][j + 3] == 'n')
&&(s[i + 2][j + 2] == 'u')
&&(s[i + 1][j + 1] == 'k')
&&(s[i + 0][j + 0] == 'e')) {
cout << i + 4 + 1 << " " << j + 4 + 1 << endl;
cout << i + 3 + 1 << " " << j + 3 + 1 << endl;
cout << i + 2 + 1 << " " << j + 2 + 1 << endl;
cout << i + 1 + 1 << " " << j + 1 + 1 << endl;
cout << i + 0 + 1 << " " << j + 0 + 1 << endl;
return 0;
}
// 左下→右上
if ((s[i + 4 - 0][j + 0] == 's')
&&(s[i + 4 - 1][j + 1] == 'n')
&&(s[i + 4 - 2][j + 2] == 'u')
&&(s[i + 4 - 3][j + 3] == 'k')
&&(s[i + 4 - 4][j + 4] == 'e')) {
cout << i + 4 - 0 + 1 << " " << j + 0 + 1 << endl;
cout << i + 4 - 1 + 1 << " " << j + 1 + 1 << endl;
cout << i + 4 - 2 + 1 << " " << j + 2 + 1 << endl;
cout << i + 4 - 3 + 1 << " " << j + 3 + 1 << endl;
cout << i + 4 - 4 + 1 << " " << j + 4 + 1 << endl;
return 0;
}
// 右上→左下
if ((s[i + 0][j + 4 - 0] == 's')
&&(s[i + 1][j + 4 - 1] == 'n')
&&(s[i + 2][j + 4 - 2] == 'u')
&&(s[i + 3][j + 4 - 3] == 'k')
&&(s[i + 4][j + 4 - 4] == 'e')) {
cout << i + 0 + 1 << " " << j + 4 - 0 + 1 << endl;
cout << i + 1 + 1 << " " << j + 4 - 1 + 1 << endl;
cout << i + 2 + 1 << " " << j + 4 - 2 + 1 << endl;
cout << i + 3 + 1 << " " << j + 4 - 3 + 1 << endl;
cout << i + 4 + 1 << " " << j + 4 - 4 + 1 << endl;
return 0;
}
}
}
}
return 0;
}正しく書けていますが、煩雑なプログラムになっています。
