Help us understand the problem. What is going on with this article?

ABC122 C - GeT AC(300点)

More than 1 year has passed since last update.

問題概要

問題のリンク

$A$, $C$, $G$, $T$ からなる長さ $N$ の文字列 $S$ が与えられます。
文字列$S$に以下の操作を$Q$回行え。

整数 $l_i,r_i (1≤l_i $S$の先頭から $l_i$ 文字目から $r_i$ 文字目までの (両端含む) 部分文字列を考える。この文字列に ACは部分文字列として何回現れるか出力せよ。

制約条件

  • $2 \leqq N \leqq 10^5$
  • $1 \leqq Q \leqq 10^5$
  • $S$は長さ$N$の文字列である。
  • $S$の各文字は $A$, $C$, $G$, $T$ のいずれかである。
  • $1 \leqq l_i < r_i \leqq N$

考えたこと

文字列$S$から、$S[l-1]$から$S[r-1]$までを切り取り、判定していこうと思ったがこの場合計算量が$0(N^2)$で最大$O(10^{10})$になってしまう。圧倒的TLE。

なので$O(N)$に収めないといけない。

文字列$S$が与えられた時点で、$AC$の数が決まっているため、文字列$S$において、0~N文字目までのACの出現回数の累積和$t[i]$をとっていく。
あとは$t[r]-t[l]$が答えとなる。

解答

c.cs
using System;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int n = a[0];
        int q = a[1];
        char[] s = Console.ReadLine().ToCharArray();
        for (int i = 0; i < n-1; i ++) {
            if (s[i]=='A' && s[i+1]=='C') s[i] = 'a';
        }
        int[] t = new int[n];
        t[0] = 0;
        for (int i = 0; i < n-1; i ++) {
            if (s[i]=='a') t[i+1] = t[i]+1;
            else t[i+1] = t[i];
        }
        for(int i = 0; i < q; i ++) {
            int[] b = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int l = b[0]-1;
            int r = b[1]-1;
            Console.WriteLine(t[r]-t[l]);
        }
    }
}
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away