ABC122 C問題 GeT AC を累積和で解く
累積和のアルゴリズムの勉強のためにABC122 C問題を解いて、解説します。
A, C, G, Tという文字からなる文字列が与えられた時に、指定された区間でACは何回あらわれるか求める問題です。
文字列の長さNは、指定される区間(クエリ)の個数Qは
単純にクエリごとにN文字を捜索していては、になってしまうので、工夫が必要です。
累積和の考え方でいくと、事前に区間ごとにACの累積出現回数を計算することを考えます。
そして、区間a文字目〜b文字目の間の出現回数を求められたら、「最初からb文字目までの出現回数」から「最初からa文字目までの出現回数」を引いて求めます。
問題のサンプルでは、"ACACTACG"という文字列が与えられて、3文字目から7文字目でACが出現する回数を聞かれています。
配列のインデックスは0から始まるので、累積和の配列をaccとすると、acc[6] - acc[2] = 3 - 1 = 2 という風に計算できるように累積和を記録する配列を作ります。
N, Q = map(int, input().split()) S = input() acc = [0 for _ in range(N + 1)] for i in range(1, N): if S[i - 1] == 'A' and S[i] == 'C': acc[i] = acc[i - 1] + 1 continue acc[i] = acc[i - 1] for _ in range(Q): l, r = map(int, input().split()) print(acc[r - 1] - acc[l - 1])
典型的な累積和の問題でした。