文系ギャルが0から始める競技プログラミング#24

Intro

この記事は不定期連載です。
↓最初の一本はこちら↓
文系ギャルが0から始める競技プログラミング#0

↓直前の記事はこちら↓
文系ギャルが0から始める競技プログラミング#23

・ABC122C - vs文字列

新ABC発表？されましたね！！
全完ギャルを名乗れるまでは長くなりましたが…
引き続き頑張っていこうと思います。
まずは茶色目指す！

というわけで勢いに乗ってC問題解いていきたいと思います。

問題文
A,C,G,Tからなる長さNの文字列Sが与えられます。
以下のQ個の問いに答えてください。
問i(1≤i≤Q):整数li,ri(1≤li<ri≤N)が与えられる。
Sの先頭からli文字目からri文字目までの(両端含む)部分文字列を考える。
この文字列にACは部分文字列として何回現れるか。

注記
文字列Tの部分文字列とは、Tの先頭と末尾から0文字以上を取り去って得られる文字列です。
例えば、ATCODERの部分文字列にはTCO,AT,CODER,ATCODER,(空文字列)が含まれ、ACは含まれません。

制約
2≤N≤10^5
1≤Q≤10^5
Sは長さNの文字列である。
Sの各文字はA,C,G,Tのいずれかである。
1≤li<ri≤N

入力
入力は以下の形式で標準入力から与えられる。
N Q
S
l1 r1
:
lQ rQ

出力
Q行出力せよ。
i行目に問iへの答えを出力すること。
― C - GeT AC

文字列！！！！！！！！！！！！！！！
苦手な文字列ですが頑張っていきたいと思います。
指定文字数でちぎられた文字列に、"AC"が何回出てくるかを判定します。

最初文字列をsubstrを使ってちぎってから判定しようとしましたがうまく行かず。。。

天の声「累積をうまく使おう」

天啓を受けたわたしは、こうして「累積で足していったものを引き算する戦法」に切り替えたのです。。。

入力から取ってきてぶっこむあたりはいつもどおりに、
累積で足していったものを計算するために、
Countと配列Count2をつくります。

そのあと、AのとなりがCだったらカウントして、それを配列にぶっこむ式をとります。

   int Count = 0;
   int Count2[100000] = {};

for(int i=0;i<N;i++){
       if(S[i] == 'A' && S[i+1] == 'C'){
           Count++;
       }
       Count2[i+1] = Count;
   }

Count2をi+1にしたのは、Cまで含まれてないと…と思いとりあえず入れましたが、、、このあたりの添字のアレが難しい…。
（天才なので合ってたみたいでよかったけど）

あとはCount2のr[i]-1番目（ここで添字ハマりした！）と、l[i]-1番目から引き算で出せました！

あんまり関係ないですが実はわたし左右という概念に弱く、いわゆる左右盲なので、「右に曲がって」と言われ左に曲がろうとするとか、いろいろ生活に支障が出るレベルでして。

…案の定、3回ぐらい左右間違えました。

   int ans = 0;
   for(int i=0;i<Q;i++){
       ans = Count2[r[i]-1]-Count2[l[i]-1];
       cout <<  ans << endl;
   }
   return 0;
}

文字数のカウントもうちょっとスムーズにできるようにしなきゃですね。

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
int main(){
   int N,Q;
   cin >> N >> Q;
   string S;
   cin >> S;
   int l[100000],r[100000] = {};
   for(int i=0;i<Q;i++){
       cin >> l[i] >> r[i];
   }
   int Count = 0;
   int Count2[100000] = {};
   
   for(int i=0;i<N;i++){
       if(S[i] == 'A' && S[i+1] == 'C'){
           Count++;
       }
       Count2[i+1] = Count;
   }
   
   int ans = 0;
   for(int i=0;i<Q;i++){
       ans = Count2[r[i]-1]-Count2[l[i]-1];
       cout <<  ans << endl;
   }
   return 0;
}

優勝！！！！！！！！！！！！！（天才なので当然ですが）

でも、もっといい解き方や、便利なテクニックなどあったらぜひTwitterやコメントで教えてください！
あと、この問題は解いとけみたいなオススメもぜひ！！！

天才競プロerの選ぶ「この問題解いとけ100選」みたいなのないの？？？

— マリー (@CBOX360) May 9, 2019

Outro

#25に続く！(不定期連載です。)

これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。