AtCoder が提供しているABC（AtCoder Beginner Contest）329 のE問題をC++とPythonで解いてみました。ABC329は、2023年11月18日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Stamp（Difficulty : 1539）
問題はリンク先をご覧ください。
キューを使って、文字列を処理していきます。AtCoder Problems による Difficulty は 1539 でした。
解答案
この問題は、Mの制約が5以下と小さいため解くことができます。基本的な考え方は、以下となります。
操作を以下とします。
- 文字列SのM文字の部分文字列S’が以下の文字列になっているか確認する。
- S’の j 文字目（0 ≦ j < M）がTの j 文字目と一致している または ‘#’ になっている。
- この場合、S’の文字をすべて’#’に置き換える。
上記の操作を繰り返して、最終的にSの文字がすべて ‘#’ になっていれば、解答は “Yes” となります。もともとの文字が残っていれば “No” となります。最初、Sは ‘#’ を含んでいないため、SがTを1か所も含んでいないと “No” となります。
文字列を ‘#’ に入れ替えた後、文字列S全体として、置き換えた前後 M-1 文字だけしか影響を受けません。このため、新しく調べる範囲は、(M-1)×2 文字しか増えません。また、1回あたりの確認は、M回のループが必要となるため、全体としての計算量は、$O(N M^2)$ となります。前述のように M が小さいため間に合います。
C++ プログラム例（ABC329E）
置き換えた文字の近傍を置き換えるため、処理する文字の位置をキューに格納して処理します。
操作の前半の確認を関数 check として分けて実装しました（9ー26行目）。すでに確認済の場所であれば、すぐに戻ります（11－13行目、メモ化）。条件を満たす場合にキューに格納します。
最初に、文字列Sで文字列Tに一致している場所をキューに格納します（34ー36行目）。次にキューから場所を取り出して、文字列Sを必要なだけ ‘#’ に入れ替えて、その前後を確認します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int n, m;
string s, t;
vector<bool> checked;
queue <int> que;
void check(int i)
{
if (checked[i]) {
return;
}
bool result = true;
for (int j = 0; j < m; ++j) {
if ((s[i + j] != t[j])&&(s[i + j] != '#')) {
result = false;
break;
}
}
if (result) {
que.push(i);
checked[i] = true;
}
}
int main()
{
cin >> n >> m;
cin >> s >> t;
checked.assign(n - m + 1, false);
for (int i = 0; i < n - m + 1; ++i) {
check(i);
}
while (!que.empty()) {
int now = que.front();
que.pop();
for (int j = 0; j < m; ++j) {
s[now + j] = '#';
}
for (int i = max(now - m + 1, 0); i < min(now + m, n - m + 1); ++i) {
check(i);
}
}
bool result = true;
for (int i = 0; i < n; ++i) {
if (s[i] != '#') {
result = false;
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC329E）
キューは、collections.deque を使いました（2、25行目）。Python の文字列は書き換えができないため、リスト化しています（21行目）。処理の基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 329 E"""
from collections import deque
def check(i):
global m, s, t, checked, que
if checked[i]:
return
result = True
for j in range(m):
if s[i + j] != t[j] and s[i + j] != '#':
result = False
if result:
que.append(i)
checked[i] = True
n, m = map(int, input().split())
s = list(input())
t = input()
checked = [False] * (n - m + 1)
que = deque()
for i in range(n - m + 1):
check(i)
while que:
now = que.popleft()
for j in range(m):
s[now + j] = '#'
for i in range(max(now - m + 1, 0), min(now + m, n - m + 1)):
check(i)
result = True
for i in range(n):
if s[i] != '#':
result = False
print("Yes" if result else "No")こちらも「AC」と判定されました。
最後に
コンテスト中には解くことができませんでした。コンテスト後に公式解説を読み、理解したことを記事にしました。
引き続き ABC の問題を紹介していきます。
