ABC
問題
B – ABC
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…
記録
- 2021/2/5 解法わからず。コード例(2)で解説AC。
解法
A
とBC
に分けて考える。A
より右にあるBC
の個数だけ操作できる。- しかし、途中で
B
やC
が途中で出てきたらカウントをリセットする。 - うしろから考えた方が実装しやすい。
コード例
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using P = pair<int, int>; #define rep(i, n) for(int i = 0; i < (n); ++i) // using mint = modint998244353; // using mint = modint1000000007; // const int mod = 1000000007; // const ll INF = 1LL << 60; // const int INF = 1001001001; // AGC034-B // https://atcoder.jp/contests/agc034/tasks/agc034_b /** * ABCABCABC * A BC A BC A BC */ int main() { string S; cin >> S; reverse(S.begin(), S.end()); ll ans = 0; ll cntA = 0; ll cntB = 0; int n = S.size(); int i = 0; while(i < n) { if(S[i] == 'A') { cntA++; ans += cntB; i++; } else if(i < n - 1) { if(S[i] == 'C' && S[i + 1] == 'B') { cntB++; i += 2; } else { cntA = 0; cntB = 0; i++; } } else { i++; } } cout << ans << endl; return 0; }