【ABC140復習】D - Face Produces Unhappiness

ご注意

考えたことの羅列なので厳密で正しい言及がされているというわけではありません。悪しからず。

答え(mainのみ)

int main(void) {
    int N, K;
    string S;
    cin >> N >> K >> S;

    int score = 0;
    for (int i = 1; i < S.size(); i++) {
        if (S[i - 1] == S[i]) score++;
    }

    int ans = min(score + 2 * K, N - 1);
    cout << ans << endl;
    return 0;
}

ポイント

反転した範囲内の幸福な人数が変わることはない

選んだ範囲の両端については、反転後に隣にいるひとが変化するので、幸不幸が変化する可能性がある。

逆に両端以外については幸不幸は変化しない。LLやRRが連続しているところに幸福な人がおり、これは反転したところでLLがRRに、RRがLLになるだけなので、結局のところ選択した範囲内については幸不幸は変わらない。つまり、両端の人がなるべく幸せになるように選べば幸福な人数は減ることはない。
よって、最初に幸福な状態の人数を計算しておき、増やした人数を足していく。

連続したLと連続したRのグループに分け、そのグループを選択して反転させる方針で

この時、
・端っこに存在するグループを選んだ場合、幸福な人数は1人増える
→隣の1グループと結合するため。
$H =$幸せ、$U =$不幸とすると、

例1）
$(R,R)(L,L) = (H,U)(U,H)$
↓
$(R,R,R,R) = (H,H,H,U)$

・端っこ以外のグループを選んだ場合、幸福な人数は2人増える
→両隣のグループと結合するため。

例2)
$(R,R)(L,L)(R,R) = (H,U)(H,U)(H,U)$
↓
$(R,R,R,R,R,R) = (H,H,H,H,H,U)$

このため、端っこ以外のグループを優先して選んでいくのが最適となる。
2人増やす操作を進めていくと最終的にLとRのグループが一つずつの状態になり、この時は先述した通り1人しか増やせない。1人増やす操作の後は、LのみかRのみの状態になり、こうなるとグループが一つしかない以上グループを選んで反転させたところでLがRに、RがLになるだけで端の一人はどうあがいても不幸な状態のままである。

よって、操作回数に制限がない場合は、

$幸福な人の初期人数+2+2+2+・・・+2+2+1+0+0+・・・$←①

といった計算をすることになり、$K$回まで操作が行えるならば①の第$K$項までの和を求めればよいことになる。

結局、(幸せな初期人数 + 2 * 操作回数, 人数 - 1)のうち、小さいほうが答え

最終的に、端っこの1人はどうあがいても不幸な状態のままである。
ということは、言い換えればこのとき1人を除いて幸せであり、以後この状態からは変化しないのだから、幸せな人数は操作回数が無制限の場合必ず$N-1$人に落ち着く。

ここで操作回数が$K$回であると考える。
2人増やす操作を$K$回行ったとすると、

$幸福な人の初期人数 +2K$ ←②

として表せる。

$K$が十分に大きいとき、①は②の数列と比較すると、明らかに+1以後の部分から和は小さくなっている。これを具体的に見ていく。

2人増やす操作をしている間は

①：$幸福な人の初期人数 +2K$
②：$幸福な人の初期人数 +2K$

であり、1人増やす操作以後は

①：$N-1$
②：$幸福な人の初期人数+2K(①<②)$

であることがわかる。
従って、どのタイミングでも①の答えが出力されるようにすることを考えると、最終的な答えは

$min(幸福な人の初期人数 +2K,N-1)$

となる。