Official

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 X adjacent to Y and turn it into Y to get one YY, and
  • you can choose all Xs in a segment YXX…XY (one or more \(X\)s between \(Y\)s) to get one extra YY,

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 virtual Xs 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.

Sample implementation

posted:
last update: