Submission #39955523

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

void cumsum(vector<int> &vec)
{
  for (int i = 0; i < (int)vec.size() - 1; i++)
    vec[i + 1] += vec[i];
}

// 'R' について左側のみ判定
vector<bool> isok_sub(int N, string S)
{
  vector<int> sumR(N + 1, 0), sumP(N + 1, 0), sumS(N + 1, 0);
  for (int i = 0; i < N; i++)
  {
    if (S[i] == 'R')
      sumR[i + 1]++;
    else if (S[i] == 'P')
      sumP[i + 1]++;
    else
      sumS[i + 1]++;
  }
  cumsum(sumR), cumsum(sumP), cumsum(sumS);

  // 'S' のうち、左が OK であるような最も左のもの
  int j = 0;
  for (; j < N; j++)
  {
    if (S[j] != 'S')
      continue;
    
    if (sumR[j] == 0 || sumP[j] >= 1)
      break;
  }

  vector<bool> isok(N, false);
  for (int i = 0; i < N; i++)
  {
    if (S[i] != 'R')
      continue;
    if (i == 0)
    {
      isok[i] = true;
      continue;
    }
    
    if (sumR[i] - sumR[j] == 0 || sumP[i] - sumP[j] >= 1)
      isok[i] = true;
    else if (i != 0 && S[i - 1] == 'S' && (sumR[i - 1] == 0 || sumP[i - 1] >= 1))
      isok[i] = true;
  }
  return isok;
}

// 左と右をつきあわせて 'R' についてのみ判定し、個数を数える
int sub(int N, string S)
{
  string T = S;
  reverse(T.begin(), T.end());

  vector<bool> isok1 = isok_sub(N, S), isok2 = isok_sub(N, T);
  int ans = 0;
  for (int i = 0; i < N; i++)
  {
    if (isok1[i] && isok2[N - 1 - i])
      ans++;
  }
  return ans;
}

string rotate(int N, string S)
{
  string T;
  for (int i = 0; i < N; i++)
  {
    if (S[i] == 'R')
      T += 'S';
    else if (S[i] == 'S')
      T += 'P';
    else
      T += 'R';
  }
  return T;
}

int main()
{
  int N;
  string S;
  cin >> N >> S;

  string T = rotate(N, S);
  string U = rotate(N, T);
  int ans = sub(N, S) + sub(N, T) + sub(N, U);
  cout << ans << endl;
}

Submission Info

Judge Result