Face Produces Unhappiness [AtCoder Beginner Contest 140 D]

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

解説

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

400点にしてはだいぶ難しく見える。
回転というのは厄介か。
まず、重要な考察がいくつかある。

• 方向が一致してない箇所で幸福が1つ減る
  • つまり、なるべく方向を一致させたい
• 回転しても、回転した区間で方向が一致していない箇所は変化しない
  • つまり、複数の方向が一致していない区間を回転させてもその間では何も起きない

で、これらを考えていくと、回転させるのは、ある同一方向を向いている塊を回転させれば良さそうということになる。
やっと400点レベルにまで落ちてきた。
方向が一致している区間を縮約するとLRLRLRやRLRLRLになっているはず。
例えばLRLRLRの最初のRを回転させるとLLLRLRでLRLRとなり、方向が一致していない箇所が2つ減る。
なので、LかRのどちらかを貪欲に回転させて、方向不一致の区間を減らしていったときの幸福人数が答え。
幸福人数はN-(LかRのグループ数)となる。各グループで1つは幸福でないため。
自分はLRの縮約をランレングスでやったが、これはオーバーキル。

int N, K;
string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> S;
    auto rl = runLengthEncoding(S);
    int gr = rl.size();
    rep(k, 0, K) {
        if(3 <= gr)
            gr -= 2;
        else if(gr == 2)
            gr = 1;
    }
    int ans = N - gr;
    cout << ans << endl;
}