AtCoder が提供しているABC（AtCoder Beginner Contest）312 のB問題をC++とPythonで解いてみました。ABC312は、2023年7月29日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 TaK Code（Difficulty : 216）
問題はリンク先をご覧ください。
特定の9×9マスのパターンがどれだけ含まれているか確認する問題です。AtCoder Problems による Difficulty は 216 でした。
解答案
C++ プログラム例（ABC312B）
Tak Code の条件を満たすか以下の手順で確認していきます。すべて満たす場合に左上の座標を表示します。配列の添え字を0からカウントするため1を加えて表示します。
- 左上の3×3がすべて ‘#’ か確認します（17ー23行目）。
- 上記の3×3の右マスがすべて ‘.’ か確認します（24ー29行目）。
- 上記の3×3とひとつ右の列の下マスがすべて ‘.’ か確認します（30ー35行目）。
- 右下の3×3がすべて ‘#’ か確認します（37ー43行目）。
- 上記の3×3の左マスがすべて ‘.’ か確認します（44ー49行目）。
- 上記の3×3とひとつ左の列の上マスがすべて ‘.’ か確認します（50ー55行目）。
以下が、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];
}
for (int i = 0; i + 8 < n; ++i) {
for (int j = 0; j + 8 < m; ++j) {
bool result = true;
int k1, k2;
for (k1 = 0; k1 < 3; ++k1) {
for (k2 = 0; k2 < 3; ++k2) {
if (s[i + k1][j + k2] != '#') {
result = false;
}
}
}
for (k1 = 0; k1 < 3; ++k1) {
k2 = 3;
if (s[i + k1][j + k2] != '.') {
result = false;
}
}
k1 = 3;
for (k2 = 0; k2 < 4; ++k2) {
if (s[i + k1][j + k2] != '.') {
result = false;
}
}
for (k1 = 6; k1 < 9; ++k1) {
for (k2 = 6; k2 < 9; ++k2) {
if (s[i + k1][j + k2] != '#') {
result = false;
}
}
}
for (k1 = 6; k1 < 9; ++k1) {
k2 = 5;
if (s[i + k1][j + k2] != '.') {
result = false;
}
}
k1 = 5;
for (k2 = 5; k2 < 9; ++k2) {
if (s[i + k1][j + k2] != '.') {
result = false;
}
}
if (result) {
cout << i + 1 << " " << j + 1 << endl;
}
}
}
return 0;
}AtCoderのユーザ解説でうまい工夫が紹介されていました。入力例1に確認するパターンを以下のように表現していました。これを使います。
###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###このパターンを配列 base に格納して、’?’ 以外のマスが一致しているか確認します（30、31行目）。全体が短くすっきりと書けています。
#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> base {
"###.?????",
"###.?????",
"###.?????",
"....?????",
"?????????",
"?????....",
"?????.###",
"?????.###",
"?????.###"
};
for (int i = 0; i + 8 < n; ++i) {
for (int j = 0; j + 8 < m; ++j) {
bool result = true;
for (int k1 = 0; k1 < 9; ++k1) {
for (int k2 = 0; k2 < 9; ++k2) {
if ((base[k1][k2] != '?')
&&(base[k1][k2] != s[i + k1][j + k2])) {
result = false;
}
}
}
if (result) {
cout << i + 1 << " " << j + 1 << endl;
}
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC312B）
C++の2つのプログラムを移植しました。まずは丁寧にパターンを確認するプログラムを紹介します。
"""AtCoder Beginner Contest 312 B"""
n, m = map(int, input().split())
s = [input() for i in range(n)]
for i in range(n - 8):
for j in range(m - 8):
result = True
for k1 in range(3):
for k2 in range(3):
if s[i + k1][j + k2] != '#':
result = False
for k1 in range(3):
k2 = 3
if s[i + k1][j + k2] != '.':
result = False
k1 = 3
for k2 in range(4):
if s[i + k1][j + k2] != '.':
result = False
for k1 in range(6, 9):
for k2 in range(6, 9):
if s[i + k1][j + k2] != '#':
result = False
for k1 in range(6, 9):
k2 = 5
if s[i + k1][j + k2] != '.':
result = False
k1 = 5
for k2 in range(5, 9):
if s[i + k1][j + k2] != '.':
result = False
if result:
print(i + 1, j + 1)9×9マスと比較するプログラムは以下です。C++と同様すっきりと書けています。
"""AtCoder Beginner Contest 312 B"""
n, m = map(int, input().split())
s = [input() for i in range(n)]
base = [
"###.?????",
"###.?????",
"###.?????",
"....?????",
"?????????",
"?????....",
"?????.###",
"?????.###",
"?????.###"
]
for i in range(n - 8):
for j in range(m - 8):
result = True
for k1 in range(9):
for k2 in range(9):
if base[k1][k2] != '?' and \
base[k1][k2] != s[i + k1][j + k2]:
result = False
if result:
print(i + 1, j + 1)どちらも「AC」と判定されました。
最後に
B問題としては、やや実装が重たい問題だと思います（素朴なプログラムは64行でした）。コンテスト中は丁寧に書くことを意識しました。コンテスト後に解説を読み、短く書ける別解が掲載されていたため、紹介しました。
引き続き ABC の問題を紹介していきます。
