AtCoder Beginner Contest 122 C問題
C問題
素直に全探索したらO(N^2)になってしまい間に合わないので、累積和を用いて解いてみた。
もっとうまく書けるんだろうけど、まあ始めのうちは泥臭いやり方でもいいでしょ!いいはず!
#include <bits/stdc++.h> using namespace std; int main() { int N, Q; string S; cin >> N >> Q >> S; S += 'X'; // この後のfor探索でSの文字数+1まで参照してしまうため、最後に1文字追加 // 累積和を利用して 0112222333344455 のようにAC数を保存する配列を作る vector<int> vec(N + 1); vec.at(0) = 0; int ACcount = 0; for (int i = 1; i <= N; i++){ if (S.at(i-1) == 'A' && S.at(i) == 'C'){ ACcount++; vec.at(i) = ACcount; } else { vec.at(i) = ACcount; } } // r番目の値からl番目の値を引き算すれば範囲内のAC数が分かるはず for (int i = 0; i < Q; i++){ int l,r; int count = 0; cin >> l >> r; count = vec.at(r - 1) - vec.at(l - 1); cout << count << endl; } }