https://atcoder.jp/contests/abc140/submissions/15507196
https://atcoder.jp/contests/abc140/submissions/9416948
- 任意区間に対して人の位置を反転させた上で向きも反転させる
- 反転したとき「連続文字列をグループ化した個数」と「幸福度」の増減に着目する
- 連続文字列→ランレングス圧縮という気持ち
連続文字列が幸福度になるので、ランレングス圧縮したい気持ちになる。境界を適当に選んだ区間を反転させると、区間内の幸福度は不変だが、境界の幸福度が+2増加し、連続文字列をグループ化した個数が-2減少すると分かる。したがって、グループが1個になるかK回のどちらかを満たすまで反転を繰り返し、幸福度を+2ずつ増やせばO(N)で答えが得られる。ただし、グループが2個になったときは幸福度が+1しか増えないので注意。なお、O(N)で処理するところO(1)で出力することも出来るが、バグりやすいのでO(N)が無難かもしれない（ぇ
