ABC122 C - GeT AC

備忘録

問題

atcoder.jp

回答

import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, Q = il()
    S = iss()
    ret = [0] * N
    for n in range(N - 1):
        if S[n] == 'A' and S[n + 1] == 'C':
            ret[n] += ret[n - 1] + 1
        else:
            ret[n] += ret[n - 1]

    for _ in range(Q):
        l, r = il()
        print(ret[r - 2] - ret[l - 2])


if __name__ == '__main__':
    main()

考え方

探索を行う問いQは最大10 ** 5個出題される。
そのため、全ての問のl, rに対してsliceとcountを行うと、TLEになる。

Submission #11777983 - AtCoder Beginner Contest 122

高速化を行うために、
長さNの文字列Sに対して、0番目からN-1番目までに、
その時点までのACの数をあらかじめカウントした配列を作成しておく。

ACの数をカウントした配列のr番目からl番目を引くことで、
文字列Sのl ~ rまでの範囲内にいくつのACが存在しているか求めることが出来る。

イメージとしては累積和に近い？