ABC 140 | D - Face Produces Unhappiness

問題

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

解法

同じ文字列が続いている場合に幸福な人が増やせる。たとえばLLLRRと向いていればLLLが3人なので2人幸福、RRで2人なので1人幸福、合計3人が幸福である。

操作は一見複雑だが以下のように操作されたあとの文字列をみると反転しな中での幸福の人の数はかわっていないことがわかる。

関係がかわるのは反転した両端とその外側の関係だけである。

関係がどのようにかわるかを列挙すると以下のようになる。

両端が同じ文字で、外側も同じ文字で、それが異なると幸福な人を増やせる。
たかだか2つしか幸福な人を増やせないので以下のようにRとLをグループに分け変更できる回数を数えればいい。
ただし、エッジケースとして変更するもので一番右側が何になるかは気をつける。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

// ひっくり返しても関係性は両端しかかわらない
// 両端が2個かわるときだけ確認して進んでいく
int main() {
  ll n, k;
  string s;
  cin >> n >> k >> s;
  if (n == 1) {
    cout << 0 << endl;
    return 0;
  }

  ll ans = 0;
  ll group = 1;
  // 既存の数を数える + 同じ文字列が連続しているものを数える
  for (int i = 0; i < n-1; i++) {
    if (s[i] == s[i+1]) {
      ans++;
    } else {
      group++;
    }
  }
  ll gc = min(group / 2, k);  // 変更できるグループ数
  if (gc == 0) {
    cout << ans << endl;
  } else {
    ans += gc * 2;
    if (gc * 2 == group) {
      ans--;
    }
    cout << ans << endl;
  }
}

その他

解説のYouTubeのコードみたらもっと簡潔にコードをかいていた。以下抜粋。

int ans = min(score+2*k, n-1); // スコアは交換するまえの幸福な人の数

幸福な人は最大でn-1人であるのと、交換すれば2 * k人最大幸福な人を増やせるのを利用している。

参考

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