けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 140 D - Face Produces Unhappiness (緑色, 400 点)

ABC では数少ない発想力系。

問題へのリンク

問題概要

L と R から成る  N 文字の文字列  S が与えられる。文字列のスコアは次のようにして決められる。

  • 各 index i について
    • S[ i ] = 'L' ならば、i + 1 >= 0 かつ S[ i - 1 ] = 'L' のときに限り、1 を加算
    • S[ i ] = 'R' ならば、i + 1 < N かつ S[ i + 1 ] = 'R' のときに限り、1 を加算

今、文字列  S に対して、「区間を指定して区間内の 'L' と 'R' を入れ替える」という操作を  K 回まで行える。 S のスコアを最大化せよ。

制約

  •  1 \le N, K \le 10^{5}

考えたこと

とてもメタ思考的なことを言うと、「操作を最大  K 回まで行うことができる」という問題設定は、アルゴリズム的にできることがとても限られてくる。そういう問題は最終的には

  • 1 回操作するごとに、何らかの値が規則的に変化していく
  • なんらかの意味で Greedy に、順にやっていくとよい

といった解法になることがほとんどだ!!!
そしてそういう解法にもっていくためには、とにかく「操作の意味をわかりやすく言い換える」というのが大変重要になってくる。

スコアの意味を言い換える

というわけでこの問題では、まず、スコアの意味がよくわからないので、スコアをわかりやすく言い換えることを試みてみよう。たとえば、

S = LLLRRRLLLLLRLLLRRLRRRR

といった文字列であったとき、このスコアは、「L が連続した部分」と「R が連続した部分」を完全に別々に考えて合算すれば問題ないことがわかる。

そしてたとえば、

S = LLLLL

について考えると、スコアは 4 になる。ところで、"LLLLL" という文字列には、'L' と 'L' の隙間が 4 箇所ある。よって、"LLLLLLLLL" のように、同じ文字が連続している部分のスコアは

  • 文字と文字の間の隙間の個数

に一致することがわかる。このように解釈すると、結局


文字列  S (長さ  N) のスコアは、「文字と文字との間の隙間」のうち異なる文字が隣接している箇所を  a 箇所としたとき、

 N-1-a

で与えられる


ということがわかる。つまり、 N-1 箇所ある「隙間」のうち、'L' と 'R' の変わり目の個数を除いた値ということになる。

解法へ

スコアをここまで言い換えられたら、あとは単純明快。操作を行なっていくごとに「'L' と 'R' の変わり目」を減らしていけば良い。

具体的には

  • S = "LLLLLRRRLLLLRRLLLL"

といった状態のとき、たとえば "RRR" のところを反転させれば

  • S = "LLLLLLLLLLLLRRLLLL"

になる。このように、一回の操作で「'L' と 'R' の変わり目」を最大で 2 箇所ずつ消すことができる。よって求める最大値は、

  •  N - 1 - \max(a - 2K, 0)

となる。計算量は  O(N)

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

int main() {
  int N, K;
  string S;
  cin >> N >> K >> S;
  int a = 0;
  for (int i = 0; i + 1 < N; ++i) if (S[i] != S[i+1]) ++a;
  cout << N - 1 - max(a - K*2, 0) << endl;
}