#11 - 文系出身エンジニアが競プロをやる

ABC122の過去問をやりました。
特に累積和という概念に触れて、頭に落とし込むまでに時間がかかりそうだったので考えたことを以下に言語化しておきます。

AtCoder Beginner Contest 122

C - GeT AC

C - GeT AC

【問題概要】
'A', 'C', 'G', 'T' からなる長さNの文字列Sが与えられます。
以下のQ個の問いに答えてください。

Sのl文字目からr文字目までに"AC"が何度出現するかを答えなさい。
制約

・2≤N≤10^5
・1≤Q≤10^5

例

・N=8,Q=3
・S="ACACTACG"
・(l,r)=(3,7),(2,3),(1,8)

解答（コード）

#include <iostream>
#include <string>
#include <cstdlib>
 
using namespace std;
 
typedef long long int ll;
#define REP(i, I, N) for (int i = I; i < N; ++i)
#define rep(i, N) REP(i, 0, N)
 
int main() {
    int N, Q, s1, s2, ans = 0;
    cin >> N >> Q;
    char s[3]; // 結合文字列を入れる
    string S;
    string match = "AC";
    cin >> S;
    rep(i, Q) {
        ans = 0;
        cin >> s1 >> s2;
        REP(j, 1, S.length()) {
            sprintf(s, "%c%c", S[i], S[j]);
            if (s1 <= j && j <= s2 && s == match) ans++;
        }
        cout << ans << "\n";
    }
    return 0;
}

最初は文字列Sを順にループさせてACにマッチする数を数えようとしていました。実際には計算コストが高く、正解はしているようだがTLEになってしまう。計算量を減らす努力をしないといけないですね。
以下だと O(Q(N-1)) になりそう。
（尚メモリバッファの管理ができてなくて、不正解になったりしてました）

以下が解説等を読みながら書き直したものです。

再解答（コード）

#include <iostream>
#include <vector>
#include <string>

using namespace std;

typedef long long int ll;
#define REP(i, I, N) for (int i = I; i < N; ++i)
#define rep(i, N) REP(i, 0, N)

int main() {
    int N, Q;
    cin >> N >> Q;
    string str;
    cin >> str;

    vector<int> vec(N + 1, 0);
    rep(i, N) {
        if (i + 1 < N && str[i] == 'A' && str[i + 1] == 'C') vec[i + 1] = vec[i] + 1;
        else vec[i + 1] = vec[i];
    }

    rep(i, Q) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        cout << vec[r] - vec[l] << "\n";
    }
    return 0;
}

正解の解答はこちらです。
けんちょん氏の累積和の記事を読みつつ整理しました。

前計算（累積和）を行うことで、それぞれを O(1) で計算できるため、全体をO(N) の計算時間で求めることが可能という理解です。
前処理大切なんだなーと強く実感しました。

熟読して、過去問こなして頭に叩き込もうと思います…。
C問題楽に解けるようになりたい！

累積和を何も考えずに書けるようにする！ - Qiita

尚char / char* / stringのようなポインタの概念について理解が浅い感じ…
慣れてないだけだろうか

Part4 誰もがつまずくポインタを完璧理解

おわりに

GW中は結構数学の勉強をしてたんですが高校数学の初歩の初歩ぐらいしかできなかったので時間ある時ゴリゴリ進めたいな…。
GW明けから仕事キツめで半身持っていかれたのが原因です。

計算量オーダーの求め方の整理も頭に入れておこう…

計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita