文字列を S\(S\)R であるとみなします。つまり、前に S を \(1\) つ、後ろに R を \(1\) つ付加します。
また、付加した文字は変更できないとも取り決めます。

すると、文字列は必ず (S の連続)(R の連続)(S の連続)\(\dots\)(R の連続) の形になります。
このことから、「 R の次に S が来る箇所の個数」を \(a\) 、「隣り合う文字が相異なる箇所の個数」を \(b\) としたとき、 \(a=(b-1)/2\) が必ず成り立ちます。なので、 \(a\) を操作によって増やす代わりに \(b\) を操作によって増やすと捉えて構いません。

また、隣接する文字が異なる状態を 1 、同じ状態を 0 として、長さ \(N+2\) の SR 列を長さ \(N+1\) の 01 列に置き換えることを考えます。
例えば、 SRSSRRRRSR は 110100011 に変換されます。
SR 列において (端以外の) 特定の文字を変更することは、 01 列においてどのような意味を持つでしょうか？

SR 列における(端以外の) \(1\) 点変更は、 01 列における隣接する \(2\) つの文字を変更することにあたります。
具体例で確認すると、 SR[S]SRRRRSR \(\rightarrow\) SR[R]SRRRRSR は 1[10]100011 \(\rightarrow\) 1[01]100011 という変更に対応します。

本問題は、 01 列中の 1 を上述の隣接 \(2\) 点の変更を使ってなるべく少ない手数で増やしていく問題に帰着されます。

1 が増える時は、隣接する \(2\) つの 0 に対して変更がかかったときに限られます。
また、 01 に対して操作をかけて 10 にする (あるいはその逆) ことは、 0 をひとつ隣に動かす操作であると捉えることができます。
さらに、隣接する \(2\) つの 1 に対して操作をかける必要がないことも示せます。

よって、問題は \(2\) つの 0 をマッチングするというものに言い換えられます。
例えば 01 列が 10100101 の場合、 0 は \(2,4,5,7\) 文字目にあります。

• 全体として \(1\) を \(2\) 個増やしたい場合は \(4,5\) 文字目の 0 をマッチングさせる
• 全体として \(1\) を \(4\) 個増やしたい場合は \(2,4\) 文字目の 0 、 \(5,7\) 文字目の 0 をマッチングさせる

ことが最適であるとわかります。

ここで、 0 がどこにあるかの情報を、隣接する 0 間の距離の配列 \(D\) に取り換えます。
0 が \(2,4,5,7\) 文字目にある場合、 \(D=(2,1,2)\) です。

この \(D\) を使うと、問題は以下のように言い換えられます。

全体で 1 を \(k\) 個増やすために、 \(D\) 中から要素を \(k/2\) 個選択して和を最小化する。
ただし、( 0 をマッチングする際に同じ 0 を使い回すことはできないので、) \(D\) のうち隣接する要素を選択することはできない。

この言い換えた問題はまさに以下の問題と同等です。

• JOI ²⁰¹⁷⁄₂₀₁₈ 春季トレーニング合宿 Day4 問題1 飴 (Candies)
  • AtCoder上のジャッジ
  • 公式解説

解法だけ抜き出すと、次の貪欲法が成立します。

• \(D\) 中のある要素 \(D_i\) を選択したとする。
• このとき、 \(D_{i-1},D_{i},D_{i+1}\) を削除し、ここに \(D_{i-1}+D_{i+1}-D_i\) を挿入する。
• 上記のルールを守りながら \(D\) のうち最も小さいものを貪欲に選択することを繰り返してよい。

priority_queue と連結リストを適切に利用することで実装でき、全体の時間計算量は \(O(N \log N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int main(){
  int T;
  cin >> T;
  while(T--){
    int n;
    string s;
    cin >> n >> s;
    s="S"+s+"R";
    int val=0;
    vector<int> sam;
    for(int i=0;i<=n;i++){
      if(s[i]==s[i+1]){
        sam.push_back(i);
      }
      else{val++;}
    }
    val/=2;
    vector<int> d;
    d.push_back(1e8); d.push_back(1e8);
    for(int i=1;i<sam.size();i++){
      d.push_back(sam[i]-sam[i-1]);
    }
    d.push_back(1e8); d.push_back(1e8);
    int dl=d.size();
    priority_queue<pi,vector<pi>,greater<pi>> pq;
    vector<int> lef(dl),rig(dl);
    vector<int> alive(dl,1);
    for(int i=0;i<dl;i++){
      lef[i]=i-1;
      rig[i]=i+1;
      pq.push({d[i],i});
    }
    vector<int> res(n+1,0);
    int hand=0;
    res[hand]=val;
    while(val<(n/2)){
      auto od=pq.top(); pq.pop();
      if(alive[od.second]==0){continue;}
      hand+=od.first; val++;
      res[hand]=val;
      int el=lef[od.second];
      int er=rig[od.second];
      d[od.second]=d[el]+d[er]-d[od.second];
      pq.push({d[od.second],od.second});
      {
        alive[el]=0;
        int x=lef[el],y=rig[el];
        lef[y]=x; rig[x]=y;
      }
      {
        alive[er]=0;
        int x=lef[er],y=rig[er];
        lef[y]=x; rig[x]=y;
      }
    }
    for(int i=1;i<=n;i++){res[i]=max(res[i],res[i-1]);}
    for(int i=0;i<=n;i++){
      if(i){cout << " ";}
      cout << res[i];
    }cout << "\n";
  }
  return 0;
}