B - XYYYX Editorial by evima
Let \(x\) be the number of Xs 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 Ys and turn them into Xs, so we may assume you choose \(K\) Xs and turn them into Ys.
Intuitively,
- you can choose
Xadjacent toYand turn it intoYto get oneYY, and - you can choose all
Xs 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 virtualXs as the $0$-th and $(N + 1)$-th characters, and try to maximize the number of YYs among the $(N + 1)$ pairs of consecutive characters.
Then, the resulting string $S'$ always has $(x + 2 - K)$ Xs, 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 YYs is equivalent to minimizing $z$.
We cannot erase the segments at both ends, so we should erase as many middle segments (between Ys) as possible, which is achieved by choosing them in ascending order of length.
When \(K > x\), it is clearly disadvantageous not to choose some Xs, so we may assume you choose all Xs.
Then, you have to choose \((K - x)\) Ys to turn them into Xs. From a different perspective, out of the \((N - x)\) Ys, \((N - K)\) will not be chosen and remain to be Ys.
Here, if we invert the Xs and Ys in the input string, the problem can be seen as choosing \((N - K)\) from the \((N - x)\) Xs and turn them into Ys, which can be reduced to the former case.
posted:
last update: