B - XYYYX Editorial by evima
Let \(x\) be the number of X
s in \(S\).
If \(x = N\), the answer is \(0\) if \(K \le 1\) and \(K - 1\) if \(K > 1\).
Below, assume \(x < N\).
When \(K \le x\), it is clearly disadvantageous to choose Y
s and turn them into X
s, so we may assume you choose \(K\) X
s and turn them into Y
s.
Intuitively,
- you can choose
X
adjacent toY
and turn it intoY
to get oneYY
, and - you can choose all
X
s in a segmentYXX…XY
(one or more \(X\)s between \(Y\)s) to get one extraYY
,
so you should choose such segments YXX…XY
greedily in ascending order of length.
After pre-computations such as counting those segments for each length naively, the problem can be solved in a total of \(\mathrm{O}(N)\) time.
The validity of the greedy strategy
Let us add virtualX
s as the $0$-th and $(N + 1)$-th characters, and try to maximize the number of YY
s among the $(N + 1)$ pairs of consecutive characters.
Then, the resulting string $S'$ always has $(x + 2 - K)$ X
s, begins with X
, and ends with X
.
Thus, if we let $z$ be the number of maximal segments consisting of X
in $S'$ (corresponding to the above segments YXX...XY
and both ends), the numbers of XX
, XY
, YX
, YY
in $S'$ are:
$$x + 2 - K - z, \ \ z - 1,\ \ z - 1, \ \ N + 1 - x + K - z$$,
respectively.
$N$, $K$, and $x$ are fixed values in the input, so maximizing the number of YY
s is equivalent to minimizing $z$.
We cannot erase the segments at both ends, so we should erase as many middle segments (between Y
s) as possible, which is achieved by choosing them in ascending order of length.
When \(K > x\), it is clearly disadvantageous not to choose some X
s, so we may assume you choose all X
s.
Then, you have to choose \((K - x)\) Y
s to turn them into X
s. From a different perspective, out of the \((N - x)\) Y
s, \((N - K)\) will not be chosen and remain to be Y
s.
Here, if we invert the X
s and Y
s in the input string, the problem can be seen as choosing \((N - K)\) from the \((N - x)\) X
s and turn them into Y
s, which can be reduced to the former case.
posted:
last update: