D. Diverse Garland

• Quiz
  • https://codeforces.com/contest/1108/problem/D
• AC
  • https://codeforces.com/contest/1108/submission/87500494
• 解法
  • (公式editorialがないので書いておく)
  • dp[i][j] i文字まで見て、そこで使った文字がjであるときの最小の交換回数
  • dpテーブルサイズは dp[N][3]
  • 後ろから復元する。最小値をたどるだけでなく、同じ文字を連続で選んではいけないことに注意

ll f(char c){
  if(c=='R') return 0;
  if(c=='G') return 1;
  if(c=='B') return 2;
}

char g(ll v){
  if(v==0) return 'R';
  if(v==1) return 'G';
  if(v==2) return 'B';
}

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

    // input
    ll N; 
    cin>>N;

    string s;cin>>s;

    VV dp(N, VI(3, inf));

    dp[0][0]=1;
    dp[0][1]=1;
    dp[0][2]=1;
    dp[0][f(s[0])]=0;

    FOR(i,1,N){
      char c = s[i];
      ll v = f(c);

      // color j to k
      rep(j,3){
        rep(k,3){
          if(j==k) continue;
          chmin(dp[i][k], dp[i-1][j] + (v!=k));
        }
      }
    }

    ll mi = inf;
    rep(i,3){
      chmin(mi, dp[N-1][i]);
    }
    p(mi);

    VI Ans;
    rep(i,3){
      if(dp[N-1][i]==mi){
        Ans.push_back(i); break;
      }
    }
    // 復元
    for(int i=N-2; i>=0; i--){
      ll mi=inf;
      ll min_j=-1;
      rep(j,3){
        if(Ans.back()==j) continue;
        if(dp[i][j]<mi){
          mi = dp[i][j];
          min_j = j;
        }
      }
      Ans.push_back(min_j);
    }

    reverse(ALL(Ans));
    for(ll a : Ans){
      cout << g(a);
    }
    cout << endl;

    return 0;
}