AGC Language

AtCoder

IDagc072_b

Time2000ms

Memory256MB

Difficulty—

An AGC word is a string of length at least $2$ that contains the same number of `A`’s and `C`’s, and in every prefix, `A`’s make up at least half of the characters. You are given a string $S$ of length $2N$ consisting of $N$ `A`’s and $N$ `C`’s. For each $k = 1, 2, \dots, K$, answer the following question. > A blackboard shows a string that is a concatenation of $k$ copies of $S$. To turn it into an AGC word, perform the operations below in the order written: > > 1. Perform **exactly once**: > * Choose integers $(l, r)$ $(1 \le l \le r \le 2kN)$ and reverse the $l$\-th through $r$\-th characters of the string. > 2. Perform **zero or more times**: > * Swap two adjacent characters of the string. > > What is the minimum number of swaps required? Notes on prefix A string $Y$ is a prefix of $X$ if and only if $1 \le |Y| \le |X|$ and the first $|Y|$ characters of $X$ equal $Y$. For example, `ATC` is a prefix of `ATCODER`, but `AGC` and `ATCODERGRANDCONTEST` are not. ## Constraints * $1 \le N \le 1\,000\,000$ * $1 \le K \le 300\,000$ * $S$ is a length‑$2N$ string consisting of $N$ `A`’s and $N$ `C`’s. * $N$ and $K$ are integers. ## Input The input is given from Standard Input in the following format: $N$ $K$ $S$ [samples]

Samples

Input #1

1 2
AC

Output #1

0
0

For $k = 1$, the initial string is `AC`;  
For $k = 2$, it is `ACAC`.
Both are already AGC words, so choosing, say, $(l, r) = (1, 1)$ yields $0$ swaps.

Input #2

5 1
CACAAACCCA

Output #2

1

For $k = 1$, the string is `CACAAACCCA`. By following the steps below, the sequence needs only one swap:

1.  Choose $(l, r) = (1, 4)$ and reverse the $1$\-st through $4$\-th characters. The string is now `ACACAACCCA`.
2.  Swap the $9$\-th and $10$\-th characters. The string is now `ACACAACCAC`, which is an AGC word.

Input #3

10 10
ACCCAAAACCCACCACAACA

Output #3

Input #4

50 10
ACCCCACAACAAAACCAACCCCACCAACACCAAAACACACAAAACCCCCACCAACACAACAACCCCAACAAACCCAACACACCCACACCAAACCCAAACA

Output #4

Input #5

72 10
CCCCACAAAAACCCACACCAAACCACCCCCAAAAACACCACCCCCAAAAAAACAAAAAACCCCCCACCCAAACAACACCACCACAAACCCAACCAACAACCCAAAACAACCCCACCACACACCACACCCACAAACACAACAACA

Output #5

API Response (JSON)

{
  "problem": {
    "name": "AGC Language",
    "description": {
      "content": "An AGC word is a string of length at least $2$ that contains the same number of `A`’s and `C`’s, and in every prefix, `A`’s make up at least half of the characters. You are given a string $S$ of lengt",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc072_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "An AGC word is a string of length at least $2$ that contains the same number of `A`’s and `C`’s, and in every prefix, `A`’s make up at least half of the characters. You are given a string $S$ of lengt...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments