[AtCoder] ABC 140 D – Face Produces Unhappiness

問題

方針

幸福でない人に着目して考えます。幸福でない人の文字列は、”RL” または “LR” となっているので、同じ文字が連続する文字列は幸福である人を含んでいるので、\( S \) を圧縮します。例えば、”RLLRRL” という文字列は、”RLRL” となります。

圧縮された文字列を \( T \) とすると、\( T \) は、”LRLR…” または、”RLRL…” のような文字列になることが分かります。\( T \) に対して、”R” を “L” にする、または “L” を “R” にするという操作を行い文字を全て “L” または “R” にすることを考えます。全て同じ文字にするために必要な操作回数は、

\[\lfloor \dfrac{|T|}{2} \rfloor\]

回となります。例えば、\( |T| = 1 \) のとき、\( S \) はすべて同じ文字であるので、\( K \) 値に依らず、\( N – 1 \) が答えになります。以上より、求める答えは、

\[N – \max(1, |T| – 2K)\]

となります。\( T \) の先頭の文字に合わせるように操作することで、一回の操作につき新たに \( 2 \) 人幸福な人が増えることになります。

コード