ABC 140 | D - Face Produces Unhappiness

문제.

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

해법

같은 문자열이 연속으로 나오면 행복한 사람이 늘어난다.예를 들어LLLRRLLL3명이어울린다면2명이행복하고RR2명이어서1명이행복하고합계3명이행복하다.
조작은 언뜻 보기에는 복잡하지만 조작 후의 문자열을 보면 반전 상태에서 행복한 사람의 수는 변화가 없다는 것을 알 수 있다.

반전된 양쪽과 외부의 관계만이 관계를 바꿀 수 있다.
관계가 어떻게 변화하는지 다음과 같이 열거한다.

양쪽 모두 같은 문자이고 바깥쪽도 같은 문자여서 다르면 행복한 사람이 늘어난다.
행복한 사람을 최대 두 명까지 늘릴 수 없기 때문에 다음과 같은 방식으로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;
  }
}

기타

해설된 유튜브 코드를 보고 코드를 더 간결하게 그렸다.이하 발췌문.

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

행복한 사람이 가장 큰 사람n-1인데, 교환하면2 * k 가장 큰 행복을 증가시키는 사람을 이용한다.

참고 자료

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