AtCoder Regular Contest 157
翻译中…
Problem Statement
翻译中…
You are given a string $S$ of length $N$ consisting of X and Y. You will choose $K$ characters at distinct positions in $S$ and change each of them: X becomes Y and Y becomes X. Find the maximum possible number of pairs of consecutive Ys in the resulting string.
翻译中…
Constraints
翻译中…
$1 \leq N \leq 2 \times 10^5$$0 \leq K \leq N$$S$is a string of length$N$consisting ofXandY.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
N K
S翻译中…
Output
翻译中…
Print the maximum possible number of pairs of consecutive Ys in the resulting string.
翻译中…
样例
Input #1
5 1
XYXYX
Output #1
2
You will choose one character.
- If you choose the $1$-st character, the resulting string is `YYXYX`, with one pair of consecutive `Y`s at positions $1, 2$.
- If you choose the $2$-nd character, the resulting string is `XXXYX`, with no pair of consecutive `Y`s.
- If you choose the $3$-rd character, the resulting string is `XYYYX`, with two pairs of consecutive `Y`s at positions $2, 3$ and $3, 4$.
- If you choose the $4$-th character, the resulting string is `XYXXX`, with no pair of consecutive `Y`s.
- If you choose the $5$-th character, the resulting string is `XYXYY`, with one pair of consecutive `Y`s at positions $4, 5$.
Thus, the sought maximum number is $2$.
Input #2
5 4
XYXYX
Output #2
2
It is optimal to choose the $1$-st, $2$-nd, $3$-rd, and $5$-th characters to get `YXYYY`, or choose the $1$-st, $3$-rd, $4$-th, and $5$-th characters to get `YYYXY`. Note that you may not choose a character at the same position multiple times.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。