D. Polycarp and Div 3

• Quiz
  • https://codeforces.com/contest/1005/problem/D
• AC
  • https://codeforces.com/contest/1005/submission/100175976
• 解説
  • 各文字をmod3しておく
  • 文字列を後ろから見て、今まで見た数値の部分集合で3の倍数が作れるなら+1して、見た集合を空にする

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    string s;cin>>s;
    ll N = s.size();

    rep(i,N){
      char c = s[i];
      ll v = c-'0';
      v %= 3;
      c = v + '0';
      s[i]=c;
    }
    debug(s);
    reverse(ALL(s));
    
    ll cnt=0;
    VI C(3);
    for(char c : s){
      if(c=='0'){
        cnt++;
        rep(i,3)C[i]=0;
        continue;
      }
      // 1 or 2
      ll v = c-'0';
      C[v]++;
      if(C[1]>=3 or C[2]>=3 or C[1]>=1 && C[2]>=1){
        cnt++;
        rep(i,3)C[i]=0;
      }
    }
    p(cnt);
    
    return 0;
}