[AtCoder] ABC 140 D – Face Produces Unhappiness

2019年9月8日

問題

方針

幸福でない人に着目して考えます。幸福でない人の文字列は、"RL" または “LR" となっているので、同じ文字が連続する文字列は幸福である人を含んでいるので、\( S \) を圧縮します。例えば、"RLLRRL" という文字列は、"RLRL" となります。

圧縮された文字列を \( T \) とすると、\( T \) は、"LRLR…" または、"RLRL…" のような文字列になることが分かります。\( T \) に対して、"R" を “L" にする、または “L" を “R" にするという操作を行い文字を全て “L" または “R" にすることを考えます。全て同じ文字にするために必要な操作回数は、

\[\lfloor \dfrac{|T|}{2} \rfloor\]

回となります。例えば、\( |T| = 1 \) のとき、\( S \) はすべて同じ文字であるので、\( K \) 値に依らず、\( N – 1 \) が答えになります。以上より、求める答えは、

\[N – \max(1, |T| – 2K)\]

となります。\( T \) の先頭の文字に合わせるように操作することで、一回の操作につき新たに \( 2 \) 人幸福な人が増えることになります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
  int N, K;
  cin >> N >> K;
  string S;
  cin >> S;
  int cnt = 0;
  vector<char> v;
  v.push_back(S[0]);
  for (int i = 1; i < N; i++) {
    if (v.back() != S[i]) v.push_back(S[i]);
  }
  
  int ans = N - max(1, (int)v.size() - 2 * K);
  cout << ans << "\n";
  return 0;
}