競プロ解法メモ

はじめに

競プロを解いていて、奇跡的に自分で思いつけた解法を記録しておく。
忘れないようにするのが１番だが、どこにも記録しないのは自分が困るのでメモする。

f(b)-f(a) を行う

a番目～b番目までといった特定範囲に含まれる何かを膨大な回数求めるときに用いる。
上手く日本語にできないが、以下のような問題を解くときに使う。

A, C, G, T からなる長さ N の文字列 S が与えられます。
以下の Q 個の問いに答えてください。

問 i (1 ≤ i ≤Q): 整数 li​ ,ri (1 ≤ li <ri ≤N) が与えられる。
S の先頭から li​ 文字目から ri​ 文字目までの (両端含む) 部分文字列を考える。
この文字列に AC は部分文字列として何回現れるか。

問題引用元
ABC122 C

上記の場合、毎回 li から ri に含まれる AC を求めていると時間がかかりすぎるので、事前に i 番目までに含まれる AC の数を求めておく。
i 番目までに含まれる数をf(i)とする。
そうすることで、Q 個の問いを解くときに、 f(ri)-f(li) を求めるだけでよくなる。

実際に上記の問題を解いた時のコードは以下となる。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
	long n, q;
	cin >> n >> q;

	string s;
	cin >> s;

	vector<long> sl(n); // iまでに含むACの数を記録
	long cnt = 0;
	for (long i = 0; i < n - 1; i++)
	{
		if (s[i] == 'A' && s[i + 1] == 'C') cnt++;
		sl[i + 1] = cnt;
	}

	vector<long> ans(q);
	long l, r;
	for (long i = 0; i < q; i++)
	{
		cin >> l >> r;
		ans[i] = sl[r - 1] - sl[l - 1];
	}

	for (long i = 0; i < q; i++) cout << ans[i] << endl;
}