なるほど。このあたりから、問題文どおりに素直に探索するようなコーディングでは、時間切れになるのか。 その前に、言語選択を間違えたり、&& を || と書き間違えたりしてミス連発したりしたんだけど。
ということで、一回全部数えておいて再利用することで、問題の規模を N*M から 1*M に減らすとゆー基本ぱたんに遭遇。
C++ は楽でいいなぁ。C だったら int a[n+1]; のとこめんどくさそう（感想）。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, q;
cin >> n >> q;
string s;
cin >> s;
int a[n+1]; a[0] = 0;
int ct = 0;
for (int i = 0; i < n - 1; i++){
if (s[i]=='A' && s[i+1] == 'C'){
ct++;
}
a[i+1] = ct;
}
for (int i = 0; i < q; i++){
int l, r;
cin >> l >> r;
int ans = a[r-1] - a[l-1];
cout << ans << endl;
}
}
工夫したのは、端の処理を単純化するための、ダミーの a[0]=0 くらいですかね。あと、右端もマイナス１するのは要注意（これは事前の数え方による）。
とりあえず、C++ 版と同じように書いてみる。cin の代わりになるようなユーティリティ関数を用意していくことになるんだなぁ。
using System;
using System.Linq;
using static System.Console;
class AtCoder
{
public static void Main()
{
var t = ReadIntArray();
int n = t[0];
int q = t[1];
var s = ReadLine();
var a = new int[n]; a[0] = 0;
int ct = 0;
for (int i = 0; i < n - 1; i++){
if (s[i] == 'A' && s[i+1] == 'C'){
ct++;
}
a[i+1] = ct;
}
for (int i = 0; i < q; i++){
var x = ReadIntArray();
int l = x[0];
int r = x[1];
WriteLine(a[r-1] - a[l-1]);
}
}
static int[] ReadIntArray()
{
return ReadLine().Split().Select(x => int.Parse(x)).ToArray();
}
}
とりあえず、これでいいと思うんだけど、cobalt1024 さんのやつ がちょっと気になる。 もうちょっと C# に慣れたら見直してみよう。
cunitac さんのやつがいいなと思いながら、自分で書いてみる（かなり影響されてしまった）。
import Control.Monad
import Data.Vector.Unboxed ((!))
import qualified Data.Vector.Unboxed as V
main = do
[_, q] <- map read.words <$> getLine
s <- getLine
let memo = V.fromList $ f (0::Int) s
f n [] = [n]
f n ('A':'C':cs) = n:n:f (n+1) cs
f n (c:cs) = n:f n cs
solve 0 = return ()
solve q = do
[l, r] <- map read.words <$> getLine
print (memo!r - memo!l)
solve (q-1)
solve q
ああ、そうか。メモをこうやってつくれば、使うときに添え字ずらさなくていいのね。