AtCoder: ABC140-D Face Produces Unhappiness (400)

問題はこちら

長さ $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 R → LL LL LL R
R LLLL R → R RRRR R

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

L RRRRR → R RRRRR
L RRRRR → L 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

ひらめの日常

日常のメモをつらつらと

AtCoder: ABC140-D Face Produces Unhappiness (400)

問題はこちら

考え方

解答