AtCoder ABC 174 D - Alter Altar (400点)

https://gyazo.com/e818e1924396efb0bb7f6c88b46ca74d

考察履歴

2個の石の入れ替えまたは1個の石の色変えができる

それによって$ WRの並びが無いように石を並べる問題

最終結果の形を考えると$ R...RW...Wとなっていれば良い

2種類の操作が可能だが、その操作を組み合わせることで最適解となることはあるだろうか？

なんとなく、なさそう。。。

色変えのみで終わらす場合、少ない方の文字数分変更すれば良い？

という実装を本番では行ったが、コンテスト後のタイムライン見ていると、全て石入れ替えのみで良い

不要コード

最終結果の形が$ R...RW...Wとなっていれば良いので、

左端の$ Wを右端へ、右端の$ Rを左端にするように入れ替えしていけば良い

どの範囲で入れ替えを行えば良いか？

左端から$ Rの個数分見れば良い。その部分が全て$ Rになっていれば最終結果の形と判断できるので。

よって、答えは左端から$ Rの個数分見て、その中に含まれる$ Wの個数となる

ACコード

code:python

import sys

import math

sys.setrecursionlimit(10 ** 8)

ini = lambda: int(sys.stdin.readline())

inm = lambda: map(int, sys.stdin.readline().split())

inl = lambda: list(inm())

ins = lambda: sys.stdin.readline().rstrip()

debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()

c = input()

R = c.count('R')

left = c:R

ans = left.count('W')

print(ans)