D - Face Produces Unhappiness

Quiz

https://atcoder.jp/contests/abc140/tasks/abc140_d

Submission

https://atcoder.jp/contests/abc140/submissions/7498421

解法

  • editorialの別解の方だと楽です（別解じゃない方も通したけど苦労した）。つまり、
  • 連続したL, Rは圧縮して1文字にする
  • 例：LLRRLL => LRL
  • 最大K回flipする(flipとは、LをRに、RをLにすること)
  • flipの位置は、圧縮した文字列の奇数番目のみ、または偶数番目のみとする（２パターン試す）
  • どちらのパターンでも、処理後に増えた幸せを計測し、maxを取って初期幸せと足せばよい
  • 詳しくはコメントを多めに書いたコードを参照（上記）