文系ギャルが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に続く！(不定期連載です。)
これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。