AtCoder が提供しているABC（AtCoder Beginner Contest）287 のD問題をC++とPythonで解いてみました。ABC287は、2023年1月28日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Match or Not（Difficulty : 796）
問題はリンク先をご覧ください。
下準備をすることにより間に合う問題です。AtCoder Problems による Difficulty は 796 でした。
解答案
問題文に従い、S’ を生成して、T と比較して、”Yes” か “No” を出力するプログラムを紹介します。プログラムでは、S’ を変数 temp_t としています。
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s, t;
cin >> s >> t;
for (int i = 0; i <= t.length(); ++i) {
string temp_t = s.substr(0, i) + s.substr(s.length() - t.length() + i);
bool result = true;
for (int j = 0; j <= t.length(); ++j) {
if ((temp_t[j] != '?')&&(t[j] != '?')&&(temp_t[j] != t[j])) {
result = false;
break;
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}文字列 T の長さの上限がほぼ 3 × 105 です。一方、内側のループは、T の長さの二乗の回数演算するため、残念ながらいくつかのテストケースで TLE（Time Limit Exceeded）判定となりました。
計算量を少なくする工夫が必要になります。
二つの Bool 型の配列 left と right を導入します。
left[i] は、文字列 S と T の先頭（左）から、i 文字が一致しているか、’?’ 込みで判断した内容を保持しておきます。
right[i] は、left と逆に文字列 S と T の最後（右）から、i 文字が一致しているか、’?’ 込みで判断した内容を保持しておきます。
配列 left と right をあらかじめ計算しておけば、S’ と T が一致するかは、left[i] とright[|T| – i] の論理積によって判断できます。
C++ プログラム例（ABC287D）
配列 left と right は、ある添え字 i で false になれば、それ以降の値は、すべて false になります（14-15行、18-19行）。
S’ が T と一致判定は、すっきりと書けています（23行目）。
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s, t;
cin >> s >> t;
vector<bool> left(t.length() + 1);
vector<bool> right(t.length() + 1);
left[0] = true;
right[0] = true;
for (int i = 0; i < t.length(); ++i) {
left[i + 1] = left[i]
&& ((s[i] == '?')||(t[i] == '?')||(s[i] == t[i]));
int si = s.length() - 1 - i;
int ti = t.length() - 1 - i;
right[i + 1] = right[i]
&& ((s[si] == '?')||(t[ti] == '?')||(s[si] == t[ti]));
}
for (int i = 0; i <= t.length(); ++i) {
if (left[i] && right[t.length() - i]) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC287D）
Python 版も、C++ を移植しました。
"""AtCoder Beginner Contest 287 D"""
s = input()
t = input()
left = [False] * (len(t) + 1)
left[0] = True
right = [False] * (len(t) + 1)
right[0] = True
for i in range(len(t)):
left[i + 1] = left[i] and \
(s[i] == '?' or t[i] == '?' or s[i] == t[i])
si = len(s) - 1 - i
ti = len(t) - 1 - i
right[i + 1] = right[i] and \
(s[si] == '?' or t[ti] == '?' or s[si] == t[ti])
for i in range(len(t) + 1):
print("Yes" if left[i] and right[len(t) - i] else "No")こちらも「AC」と判定されました。
Python は記述性が良いのですが、C++ プログラムを移植すると時間的に不利になることが多いです。しかし、このD問題については、Python 版の方が実行時間が短かったです。
最後に
あらかじめ計算することにより、繰り返されるクエリの計算量を下げる工夫は、累積和の場合と似ているかもしれません。コンテスト中にうまく気づくことができました。このような工夫で正解できるとプログラミングが楽しくなります。
引き続き ABC の問題を紹介していきます。
