ひらめの日常

プログラミングと読書と

ABC140-D Face Produces Unhappiness (400)

問題はこちら

atcoder.jp

長さ  N の文字列  S が与えられる。L は自分の左に L が来た時、R は自分の右に R が来た時、幸福になるという。以下の操作を  K 回以下繰り返して、幸福なものを最大いくつにできるか答えよ。

操作:  1 \leq l \leq r \leq N となる  l, r を選び、  [l, r] 内にある文字列を左右反転させ、方向も反転させる。

考え方

操作をする系は、その前後で何が変わるかを考えると良い(特に求める答えに関するもの)。今回の場合は、一回操作を行うたびに、その区間の両端の状態が変わる。 (いい加減こういうのに慣れたいですね...)

幸せになる数が増えるのは、LL, RR という並びが存在するときなので、操作をした時に内部の状態変化が答えに与える影響はない。しかし、両端とその隣の状態が変化し、最大でも +2 されることがわかる。

そこで、+2 を貪欲にやる方法を考えてみる。すると、同じものが続いている区間を反転すれば、両端が新しく条件を満たし、答えが +2 されると考えられる。この時点で、順番が反転することは考えなくてよくなり、向きが反転することだけ考えればよくなる。

  • LL RR LL RLL LL LL R
  • R LLLL RR RRRR R

注意するのは、以下のような時で、 +1 しかされない。

  • L RRRRRR RRRRR
  • L RRRRRL LLLLL

しかし、 +1 の操作は一回しか起こり得ないかつ、答えとしてありえる最大値 - 1 から最大値に移行する時に使用すると考えることができる。(つまり一番最後に行う。)

これらより、答えは 「min(もともと連続で続いている個数 + 2 * k, n - 1)」になる。

解答

考察が終わればいたって簡単。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {

    ll n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    ll ans = 0;
    rep(i, n - 1) {
        if (s[i] == s[i + 1]) ans++;
    }
    ans += 2 * k;
    cout << min(n - 1, ans) << '\n';
    return 0;
}

Submission #7416033 - AtCoder Beginner Contest 140