# abc122C

[Get AC (300点）](https://atcoder.jp/contests/abc122/tasks/abc122_c)

なるほど。このあたりから、問題文どおりに素直に探索するようなコーディングでは、時間切れになるのか。
その前に、言語選択を間違えたり、$<verb>{&&} を $<verb>{||} と書き間違えたりしてミス連発したりしたんだけど。

ということで、一回全部数えておいて再利用することで、問題の規模を N*M から　1*M に減らすとゆー基本ぱたんに遭遇。

## C++

C++ は楽でいいなぁ。C だったら $<verb>{int a[n+1];} のとこめんどくさそう（感想）。

$$<pre>{
#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#

とりあえず、C++ 版と同じように書いてみる。cin の代わりになるようなユーティリティ関数を用意していくことになるんだなぁ。

$$<pre>{
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 さんのやつ](https://atcoder.jp/contests/abc122/submissions/4699065) がちょっと気になる。
もうちょっと C# に慣れたら見直してみよう。

# Haskell

[cunitac さんのやつ](https://atcoder.jp/contests/abc122/submissions/4693484)がいいなと思いながら、自分で書いてみる（かなり影響されてしまった）。

$$<pre>{
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
$$}

ああ、そうか。メモをこうやってつくれば、使うときに添え字ずらさなくていいのね。