AtCoder が提供しているABC（AtCoder Beginner Contest）372 C問題をC++とPythonで解いてみました。ABC372は、2024年9月21日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Count ABC Again（Difficulty : 341）
問題の詳細は、リンク先をご覧ください。
クエリで変更した文字の前後だけ確認します。AtCoder Problems による Difficulty は 341 でした。
解答案
長さ $N$ の文字列を $Q$ 回操作すると、計算量が $O(NQ) = 4 \times 10^{10}$ となり間に合いません。
ただし、1回のクエリでは、1文字しか変わりませんから、その前後3文字以内だけを確認すれば十分です。1回のクエリ当たり $O(1)$ で判定できるため、計算量的にも間に合います。
C++ プログラム例（ABC372C）
まず初期値の文字列 $S$ に含まれる ”ABC” の個数を変数 result に格納します（12ー17行目）。
クエリ毎に以下を行います。
- 変更する文字の場所にある ”ABC” の個数を result から引きます（24ー28行目）。
- 変更した後にその前後にある ”ABC” の個数を result に加えます。（30ー34行目）。
- 変数 result の値を出力します。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, q;
cin >> n >> q;
string s;
cin >> s;
int result = 0;
for (int i = 0; i + 2 < n; ++i) {
if ((s[i] == 'A')&&(s[i + 1] == 'B')&&(s[i + 2] == 'C')) {
++result;
}
}
for (int i = 0; i < q; ++i) {
int x;
char c;
cin >> x >> c;
--x;
for (int j = max(0, x - 2); j <= x && j + 2 < n; ++j) {
if ((s[j] == 'A')&&(s[j + 1] == 'B')&&(s[j + 2] == 'C')) {
--result;
}
}
s[x] = c;
for (int j = max(0, x - 2); j <= x && j + 2 < n; ++j) {
if ((s[j] == 'A')&&(s[j + 1] == 'B')&&(s[j + 2] == 'C')) {
++result;
}
}
cout << result << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC372C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 372 C"""
n, q = map(int, input().split())
s = list(input())
result = 0
for i in range(n - 2):
if s[i] == 'A' and s[i + 1] == 'B' and s[i + 2] == 'C':
result += 1
for i in range(q):
x, c = input().split()
x = int(x) - 1
j = max(0, x - 2)
while j <= x and j + 2 < n:
if s[j] == 'A' and s[j + 1] == 'B' and s[j + 2] == 'C':
result -= 1
j += 1
s[x] = c
j = max(0, x - 2)
while j <= x and j + 2 < n:
if s[j] == 'A' and s[j + 1] == 'B' and s[j + 2] == 'C':
result += 1
j += 1
print(result)こちらも「AC」と判定されました。
最後に
クエリでは1文字しか変更しませんので、その前後だけ調べればよいことに気付けました。問題が解けるとうれしくなります。
引き続き ABC の問題を紹介していきます。
