UVa 12856 : Counting substhreengs

問題リンク : http://uva.onlinejudge.org/external/128/12856.pdf

問題概要 :
長さ10^6以下の文字列が与えられる
文字列の部分文字列のうち、数字のみを含み、それを10進数の数として見たときにその値が3の倍数であるようなものを数えよ
リーディング０も許す

解法 :
動的計画法
まず数字以外は必要ないので、文字列を数字のみを含むように分解する
後は分解された各文字列について、その部分文字列のうち３の倍数となるものをDPで数え上げる
dp[桁][余り] :＝ 数　

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
ll dp[1000010][3];

void compute(vector<string> &vec){
  ll answer = 0;
  rep(cur,vec.size()){
    string s = vec[cur];
    rep(i,(int)s.size()+1) rep(j,3) dp[i][j] = 0;
    rep(i,(int)s.size()) {
      int value = s[i] - '0';
      ++dp[i+1][value%3];
      rep(remain,3) if( dp[i][remain] ){
        int nremain = ( remain * 10 + value ) % 3;
        dp[i+1][nremain] += dp[i][remain];
      }
    }
    rep(i,(int)s.size()+1) answer += dp[i][0];
  }
  cout << answer << endl;
}

int main(){
  string s;
  while( getline(cin,s) ){
    vector<string> vec;
    string temp = "";
    rep(i,(int)s.size()){
      if( isdigit(s[i]) ) {
        temp += string(1,s[i]);
      } else if( !temp.empty() ) { vec.push_back(temp); temp = ""; }
    }
    if( !temp.empty() ) vec.push_back(temp);
    compute(vec);
  }
  return 0;
}