ABC328 C問題（Consecutive）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）328 のC問題をC++とPythonで解いてみました。ABC328は、2023年11月11日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Consecutive（Difficulty : 236）

問題はリンク先をご覧ください。

ABC328 C問題 Consecutive

同じ文字が隣り合う数を前準備で計算して質問に答えます。AtCoder Problems による Difficulty は 236 でした。

解答案

累積和の紹介

同じ文字列に対して、$Q$回の質問がされます。質問に対して、2つ隣り合う箇所をカウントすると、計算量 $O(NQ) = 9 \times 10^{10}$ となり間に合いません。

このような場合は、累積和（計算量 $O(N)$）で前準備をしておくと、質問に対して $O(1)$ で解答できるため、結果的に計算量 $O(N+Q)$ となり間に合います。

入力例1に対して、累積和を求めてみます。文字列の添え字は0からカウントします。

この問題の場合

一般的に累積和 T に対して、目的の値 [left, right) は T[right] – T[left] で求めることができます。今回の場合、l_i、r_i が1からカウントされた値となります。

• この問題の場合、2文字の組で判定されるため、l_i の値に対して、1文字多く考える必要があります（ここは注意が必要です）。1からカウントされているため1文字減らす必要があり、1文字多く考える必要があるため、結果的に l_i をそのまま使います。
• r_i は、1からカウントされているため1文字減らす必要があります。一方、r_i は開区間とするため、1加える必要があります。結果的に r_i をそのまま使います。

C++ プログラム例（ABC328C）

累積和を上の考え方で求めます（11－18行目）。質問に対しては、添え字のカウントの仕方と、求めたい値を考えると、結果的に読み込んだ l_i と r_i をそのまま使うことができます（23行目）。

以下が、C＋＋プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;

	vector<int> t(n + 1, 0);
	for (int i = 1; i < n; ++i) {
		if (s[i - 1] == s[i]) {
			t[i + 1] = t[i] + 1;
		} else {
			t[i + 1] = t[i];
		}
	}

	for (int i = 0; i < q; ++i) {
		int left, right;
		cin >> left >> right;
		cout << t[right] - t[left] << endl;
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC328C）

Python 版も基本的な考え方は同じです。以下となります。

"""AtCoder Beginner Contest 328 C"""
n, q = map(int, input().split())
s = input()

t = [0] * (n + 1)
for i in range(1, n):
    if s[i - 1] == s[i]:
        t[i + 1] = t[i] + 1
    else:
        t[i + 1] = t[i]

for i in range(q):
    left, right = map(int, input().split())
    print(t[right] - t[left])

こちらも「AC」と判定されました。

最後に

この問題は累積和を前もって計算することにより、質問の計算コストを下げることができました。うまい考えだと思います。

引き続き ABC の問題を紹介していきます。