ABC 122 C - GeT AC

atcoder.jp

初手の方針

ぱっと見で累積和で解こうとなった、結果的にこの方針は正しかった。 ARC098の問題もそうだが、1次元のある区間の値を求めるような問題は累積和にパターンマッチできるようになってきたように思う。

C - Attention

Submission #9320350 - AtCoder Beginner Contest 122

本日の気付き

累積和の作り方の話。 今回のように1つ前の値によって条件が分岐するような処理は予めstringで値を保持しておくと良い。

    ll N, Q;
    string S;
    cin >> N >> Q >> S;
    V<ll> cnt(N + 10, 0);
    for(ll i = 1; i < N; i++) {
        cnt[i + 1] = cnt[i];
        if(S[i - 1] == 'A' && S[i] == 'C') cnt[i + 1]++;
    }

提出したコードと比べると余分なフラグがなくてすっきりする。

REP(i, n) {
    char c;
    cin >> c;

    if(i == 0) {
      s[i] = 0;
    } else {
      if (c == 'C' && isA) {
        s[i] = s[i-1] + 1;
      } else {
        s[i] = s[i-1];
      }
    }

    if(c == 'A') isA = true;
    else isA = false;
  }