AtCoder Grand Contest 034 B - ABC やらかしコード

問題はこちら。問題の紹介、解説は全くしない。

atcoder.jp

AGCなのにABCという謎な問題。

以前この問題を解いて最後の一つのWAが取れず、ずっと考えていて今回一からコードを書き直すことにした。その結果依然としてWAが取れず悩んでいた。そのWAが取れたのでその経過をここに記す。

オーバーフローの可能性を考えていなかったのがまず失策。最大の場合を考える。つまりABCABCABC・・・・・ABCABの合計200000文字の文字列が入力として与えられた場合である。その場合の答えは66666 * (66666 + 1) / 2である。

この計算結果は2222211111

一方でINTの最大値は2147483647

である。

ギリギリオーバーフロー。アルゴリズム的には問題なく、答えの型をintからlong long に変更。結果AC。

一応書いたコードも載せておく。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int (i)=0;(i)<(n);(i)++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
int main() {
  string s;
  cin >> s;
  int n = s.size();
  ll res = 0;
  int start = -1;
  vector<string> ans;
  for(int i=0;i<n;i++) {
    if(s[i] == 'A') {
      if(start == -1) start = i;
      else continue;
    }
    else if(s[i] == 'B') {
      if(start == -1) continue;
      else if(i == n-1) {
        ans.emplace_back(s.substr(start, i-start));
        start = -1;
      }
      else if(s[i+1] == 'C') i++;
      else {
        ans.emplace_back(s.substr(start, i-start));
        start = -1;
      }
    }
    else if(s[i] == 'C') {
      if(start == -1) continue;
      else {
        ans.emplace_back(s.substr(start, i-start));
        start = -1;
      }
    }
  }
  if(start != -1) {
    ans.emplace_back(s.substr(start, n-start));
    start = -1;
  }
  for(int i=0;i<ans.size();i++) {
    string ss = ans[i];
    int bcNum = 0;
    for(auto it=ss.rbegin();it!=ss.rend();it++) {
      if(*it == 'C') {
        bcNum++;
        it++;
      }
      else if(*it == 'A') res += bcNum;
    }
  }

  cout << res << endl;
  return 0;
}

感想

また親の仇が増えた。オーバーフローお前もだ。