AtCoder が提供しているABC（AtCoder Beginner Contest）324 のE問題をC++とPythonで解いてみました。ABC324は、2023年10月14日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Joint Two Strings（Difficulty : 1153）
問題はリンク先をご覧ください。
左右から部分文字列となっている文字数を求めて二分探索です。AtCoder Problems による Difficulty は、1153 でした。
解答案
文字列 $S_i$ は、文字列 $T$ を左から考えて left[i] 文字を部分文字列として含むとします。同じように右から考えて right[i] 文字を部分文字列として含むとします。
言葉では分かりにくいため、入力例1で考えます。文字列 $T$ は、”bac” です。
| i | 文字列 | 左から考えた部分文字数 left[i] | 右から考えた部分文字数 right[i] |
| 0 | abba | 2文字（bとa） | 0文字 |
| 1 | bcb | 1文字（bのみ） | 1文字（cのみ） |
| 2 | aaca | 0文字 | 2文字（aとc） |
ここまで求めておけば、以下が分かります。
- $S_0$ を左側に持つ場合、$S_1$ と $S_2$ を右側に持てば合わせて “bac” を含む。
- $S_1$ を左側に持つ場合、$S_2$ を右側に持つ文字列のみ “bac” を含む。
- $S_2$ を左側に持つ場合、右側にどの文字列を持ってきても “bac” を含まない。
上記から、3通りの場合に合わせた文字列は ”bac” を含むことが分かります。
同じように left[i], right[i] を求めて、left[i] + right[j] が $T$ の文字数以上になる場合の数を求めます。具体的には、ソートした right に対して、二分探索で（$T$ の文字数 – left[i]）以上となる個数から、場合の数を求めることができます。
C++ プログラム例（ABC324E）
上の解説の手順を実装しました。
- 配列 left[i] を求めます。部分文字列として一致した文字の場所を、変数 ti に格納しておきます（16ー28行目）。
- 配列 right[i] を求めます。部分文字列として一致した文字の場所を、変数 ti に格納しておきます（29ー41行目）。
- 二分探索ができるように right をソートします（42行目）。
- 配列 right に対して（$T$ の文字数 – left[i]）以上となる要素の個数を求めて、変数 result に加えていきます（44ー47行目）。
- 変数 result を出力します（49行目）。
プログラムは少し長くなりました。ただし、コードのそれぞれの塊はやることが明確になっています。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
string t;
cin >> n >> t;
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
vector<int> left(n, 0);
for (int i = 0; i < n; ++i) {
int ti = 0;
for (int j = 0; j < s[i].length(); ++j) {
if (s[i][j] == t[ti]) {
++ti;
if (ti == t.length()) {
break;
}
}
}
left[i] = ti;
}
vector<int> right(n, 0);
for (int i = 0; i < n; ++i) {
int ti = t.length() - 1;
for (int j = s[i].length() - 1; j >= 0 ; --j) {
if (s[i][j] == t[ti]) {
--ti;
if (ti == -1) {
break;
}
}
}
right[i] = (t.length() - 1) - ti;
}
sort(right.begin(), right.end());
ll result = 0;
for (int i = 0; i < n; ++i) {
result += n - (lower_bound(right.begin(), right.end(), t.length() - left[i]) - right.begin());
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC324E）
基本的な考え方は同じです。モジュール bisect を import して、bisect.bisect_left を呼び出して二分探索しています（2、30行目）。
"""AtCoder Beginner Contest 324 E"""
import bisect
n, t = input().split()
n = int(n)
s = [input() for i in range(n)]
left = [0] * n
for i in range(n):
ti = 0
for j in range(len(s[i])):
if s[i][j] == t[ti]:
ti += 1
if ti == len(t):
break
left[i] = ti
right = [0] * n
for i in range(n):
ti = len(t) - 1
for j in range(len(s[i]) - 1, -1, -1):
if s[i][j] == t[ti]:
ti -= 1
if ti == -1:
break
right[i] = len(t) - 1 - ti
right.sort()
result = 0
for i in range(n):
result += n - bisect.bisect_left(right, len(t) - left[i])
print(result)こちらも「AC」と判定されました。
最後に
この問題は、コンテスト中に解くことができました。二分探索の考え方に慣れてきた気がします。
引き続き ABC の問題を紹介していきます。
