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;
}

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

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

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

問題概要

制約

考えたこと

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

解法へ