UVa1215

UVa1215

文字列の 0 番目から i 番目までに各文字がどれくらいあるかを前もって数えておく。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <sstream>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define VAR(a) cout << #a << " : " << a << endl;

typedef long long int lli;

using namespace std;

int main(int argc, char *argv[])
{
  int tc;
  cin >> tc;

  const int N = 10000 + 1;
  const int C = 'z' + 1;
  int cnt[C][N];

  while (tc--) {
    fill(&cnt[0][0], &cnt[C - 1][N], 0);

    int k;
    cin >> k;
    int cut[k];
    for (int i = 0; i < (int)k; ++i) {
      cin >> cut[i];
    }

    string s;
    cin >> s;
    for (int i = 0; i < (int)s.size(); ++i) {
      ++cnt[s[i]][i + 1];
    }
    for (int c = 0; c < (int)C; ++c) {
      for (int i = 1; i < (int)N; ++i) {
        cnt[c][i] += cnt[c][i - 1];
      }
    }

    vector<int> v;
    v.push_back(0);
    v.push_back(s.size());
    
    int sum = 0;

    for (int i = 0; i < (int)k; ++i) {
      int idx = distance(v.begin(), lower_bound(v.begin(), v.end(), cut[i]));
      int begin = v[idx - 1];
      int end = v[idx];
      int cost = 0;
      
      for (int c = 'a'; c <= 'z'; ++c) {
        int a = cnt[c][cut[i]] - cnt[c][begin];
        int b = cnt[c][end] - cnt[c][cut[i]];
        if (a && b) ;
        else if (a || b) ++cost;
      }
      v.push_back(cut[i]);
      sort(v.begin(), v.end());
      sum += cost;
    }
    cout << sum << endl;
  }
  return 0;
}