ABC174 D - Alter Alter

atcoder.jp

Rの左隣にWがあるとダメ．したがって，最終的には左側にRが寄っている配置になる．

問題文には，以下の二つの操作が与えられていた．

  • 石を2個選び，それらを入れ替える
  • 石を1個選び，その石の色を変える

しかし，なんとなく，入れ替えの操作だけで最小回数が達成できそうな気がした．

方針としては，「文字列に含まれるRの総数」と「Rの個数のみの累積和」を求め，「Rの総数」- 「左端から「Rの総数」番目までの累積和」を計算することで，必要な入れ替えの回数を求める．

与えられた文字列が「WRWWRWRR」なら，「Rの個数のみの累積和」は以下のようになる．

N = int(input())
C = input()

S = []
S.append(0)
for i in range(N):
    if C[i] == 'R':
        S.append(S[i]+1)
    else:
        S.append(S[i])

print(S[-1] - S[S[-1]])

所要時間

31分(Median Solve Time:確か35分)