ABC122-C GeT AC

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("8 3");
            WillReturn.Add("ACACTACG");
            WillReturn.Add("3 7");
            WillReturn.Add("2 3");
            WillReturn.Add("1 8");
            //2
            //0
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        string S = InputList[1];

        int UB = S.Length - 1;
        int[] RunSumArr = new int[UB + 1];

        for (int I = 1; I <= UB; I++) {
            if (S[I] == 'C' && S[I - 1] == 'A') {
                RunSumArr[I]++;
            }
        }

        // 累積和を求める
        for (int I = 1; I <= UB; I++) {
            RunSumArr[I] += RunSumArr[I - 1];
        }

        // クエリに回答する
        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            int L = wkArr[0] - 1;
            int R = wkArr[1] - 1;

            // Lが文字Cの位置の場合は、Lをインクリメントする
            if (S[L] == 'C') L++;

            Console.WriteLine(RunSumArr[R] - RunSumArr[L]);
        }
    }
}

解説

クエリにO(1)で回答するために、事前にACの登場数の累積和を求めて
範囲終了でのAC登場数から範囲開始でのAC登場数を引いてます。

コーナーケースとして、範囲開始がCの場合は、
範囲開始を1つインクリメントしてます。