Yahoo社のコーディングテストで悔しさを抱いて帰ってきました、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc122)にて開催されました、AtCoder Beginner Contest 122-C問題「C - GeT AC」の問題と僕との戦闘記です。

0.はじめに

1.問題文

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

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

2.制約

2 ≤ N ≤ 10⁵
1 ≤ Q ≤ 10⁵
S は長さ N の文字列である。
S の各文字は A, C, G, T のいずれかである。
1 ≤ l_i < r_i ≤ N

3.入力例

入力

8 3
ACACTACG
3 7
2 3
1 8

出力

2
0
3

4.初見の感想

部分文字列を左から走査すれば解けそう

→TLE

ACの出現位置をリストに保存することで、計算回数を減らせる

→出現位置も最悪の場合を考えると膨大な量となる

5.学びポイント

累積和を使用する

→右端の累積和から左端の累積和を減じることで、答えが出せる！

ACの2文字のAの位置で累積和を増やすか、Cの位置で増やすか

→部分文字列の左端と右端が同じになることはない(右端がCなら一文字前のAも必ず含まれる)

→Cの位置で増やす

6.コードの簡単な解説

まず、入力の値のパースを行う

        string[] temp = Console.ReadLine().Split(' ');
        int N = int.Parse(temp[0]);
        int Q = int.Parse(temp[1]);
        char[] input = Console.ReadLine().ToArray();

累積和をCの位置で計算

        int[] dp = new int[N];
        for(int i = 1; i < input.Length; i++)
        {
            if (input[i-1] == 'A' && input[i] == 'C') { dp[i] = dp[i - 1] + 1; }
            else { dp[i] = dp[i - 1]; }
        }

左端と右端で累積和の差を計算

        int[] L = new int[Q];
        int[] R = new int[Q];
        for (int i = 0; i < Q; i++)
        {
            temp = Console.ReadLine().Split(' ');
            L[i] = int.Parse(temp[0]);
            R[i] = int.Parse(temp[1]);
            Console.WriteLine((dp[R[i]-1])-dp[L[i]-1]);
        }
    }
}

7.全コード

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
class Program
{
    static void Main(string[] args)
    {
        string[] temp = Console.ReadLine().Split(' ');
        int N = int.Parse(temp[0]);
        int Q = int.Parse(temp[1]);
        char[] input = Console.ReadLine().ToArray();
        int[] dp = new int[N];
        for(int i = 1; i < input.Length; i++)
        {
            if (input[i-1] == 'A' && input[i] == 'C') { dp[i] = dp[i - 1] + 1; }
            else { dp[i] = dp[i - 1]; }
        }
        int[] L = new int[Q];
        int[] R = new int[Q];
        for (int i = 0; i < Q; i++)
        {
            temp = Console.ReadLine().Split(' ');
            L[i] = int.Parse(temp[0]);
            R[i] = int.Parse(temp[1]);
            Console.WriteLine((dp[R[i]-1])-dp[L[i]-1]);
        }
    }
}

8.最後に

累積和…覚えましたし…

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

【プログラミングコンテスト】AtCoder Beginner Contest 122③