zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC122-C「GeT AC」です。
ポイント
全探索を行うことができない問題です。$Q$個のクエリ（与えられた右端と左端の条件）に対して毎回「AC」の数を数えていたら計算量は$O(NQ)=O(10^{10})$となり，間に合いません。そこで，工夫が求められます。
今回は，メモ化の考え方を使います。累積和というやつです。あらかじめ，各文字列までの「AC」の数を数えてメモに残しておくことで，各クエリに対して一瞬答えを導くことができるようになります。クエリが与えられたときにメモから答えを導き出す計算量は$O(1)$です。計算が間に合わないときは，まずはメモ化を考えることは定石です。
おさえるべき内容
メモ化で効率UP
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
int N, Q;
string S;
int L[100010];
int R[100010];
int X[100010];
int main(){
cin >> N >> Q >> S;
rep(i, Q){
cin >> L[i] >> R[i];
// 0インデックスに揃える
L[i]--;
R[i]--;
}
int cnt = 0;
// メモを残す作業
repi(i, 0, S.size()-1){
// 最初から2文字ずつ見ていく
string s = S.substr(i, i+2);
// もし"AC"という文字列であればcntをインクリメントする
if (s[0]=='A' and s[1]=='C') cnt ++;
// iは部分文字列の最初のインデックスなのでi+1インデックスにACの数の累積和を保管していく
X[i+1] = cnt;
}
rep(i, Q){
// あとは与えられたクエリに対する答えをメモから探して出力するだけ
cout << X[R[i]] - X[L[i]] << endl;
}
}
コメント