AtCoder ABC 174D Alter Altar

問題

左から右へN個の石が並んでいる。石の種類は白もしくは赤のいづれかである。

石について、下記の操作を何回でも実行できる。

• ２個の石を選んで場所を入れ替える（隣合ってなくてよい）。
• １個の石を選んで、色を変える。

この操作を繰り返し、赤い石の左隣に白い石がないようにする。

分析

ゴール状態

まずゴールの状態 ―赤い石の隣に白い石がない― を考える。R=赤い石、W=白い石と考える。

今赤い石を任意の場所に置く。この時、赤い石の左隣には、離れていたとしても白い石はないはずである。

1：〇〇R〇〇
2：〇RR〇〇
3：RRR〇〇

次に白い石を任意の場所に置く。この時、白い石の右隣には、離れていたとしても赤い石はないはずである。

1：〇〇W〇〇
2：〇〇WW〇
3：〇〇WWW

よってゴールの状態は以下のようになる。

RR…RW…WW

入れ替え操作

次に入れ替えの動作について考える。下記のような配列について入れ替え操作を考える。

RWWRWRWWR

入れ替えは目標となる配列が決まっていなければ、操作を決定することはできない。操作を決定できなければ回数を求めることはできない。よって、目標となる配列を固定する必要がある。

初期：R W W R W R W W R
目標：R R R W W W W W W

この時すでに一致している配列については無視できる。よって下記の[]になっている位置については無視する。

初期：[R] W W R [W] R [W W] R
目標：[R] R R W [W] W [W W] W

次に操作によって目標の配列を目指す。配列の入れ替えの組み合わせとしては下記が考えられる。

パターン1: W→R
パターン2: R→W
パターン3: 入れ替える

次に入れ替えの個数を以下のように考える。

A=W→Rに入れ替える個数
B=R→Wに入れ替える個数

操作を一回実行したときに入れ替え個数の変化は以下のようになる。

パターン1: A–
パターン2: B–
パターン3: A– and B–

よってまずパターン3を実行して、その後必要に応じて、パターン1もしくは2を実行する。

上記の例ではA=2; B=3としたとき、以下の操作が最も望ましい。

A=2, B=3→[パターン3 x 2]→A=0, B=1→[パターン2 x 1]→A=0, B=0

よって操作回数はmax(A, B)となることが明らかである。

すべての配列を考える

2≤N≤200000により処理はO(N)で実施する必要がある。N^2では10^10となりTLEとなることが予測される。

考え方としては、初期状態の違いを記録しておき、一つずつ石を変化し、その変化により初期状態を更新していく。

R W W R W R W W R
W W W W W W W W W
R→W=4
W→R=0

R W W R W R W W R
R W W W W W W W W
R→W=3 (4-1)
W→R=0

R W W R W R W W R
R R W W W W W W W
R→W=3
W→R=1

これにより実行回数はO(N)となる。

実装

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


rw=C.count('R')
wr=0
ans=rw

for i in range(N):
    if C[i]=='R':
        rw-=1
    else:
        wr+=1
    ans=min(ans,max(rw,wr))
print(ans)

 

参考になる実装

print(s[:s.count("R")].count("W"))

 

例えばRWRWWRという配列を考える。この時Rは３個あるのでRRRWWWとなればよい。

R[W]R | WW[R]

RとWに区切りを入れた場合、右側のRと左側のWを入れ替えれば、目的となる配列を取得できる。左側のWの数は配列SについてS[:Rの個数]から’W’の個数を数えればよい。