시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB222100.000%

문제

$N$ 個のライトが横一列に並んでおり,左から順に $1$ から $N$ までの番号が付けられている.それぞれのラ イトの色は赤,緑,青のいずれかである.ライトの色は文字列 $S$ によって表され,ライト $i$ ($1 ≦ i ≦ N$) の 色は,$S$ の $i$ 文字目が ‘R’ のとき赤,‘G’ のとき緑,‘B’ のとき青である.

最初すべてのライトは点灯している.葵は,「$1$ 個以上 $K$ 個以下の連続するライトを選んですべて消灯さ せる」という操作を何度でも行うことができる.このとき,既に消灯しているライトを再び選んでも構わ ない.

葵は,遠くからこのライトの列を見たときにきれいな白色に見えるようにしたい.そのためには,点灯 しているライトを左から見たときの色の並びが “RGBRGB...RGB” のように “RGB”(赤緑青)の繰り返しに なっている必要がある.ただし,$1$ つも点灯しているライトが存在しない場合も条件を満たすものとする. “GBRGBR” や “RGBRG” などの色の並びは条件を満たさないことに注意せよ.

ライトと操作に関する情報が与えられたとき,葵が最小で何回操作を行う必要があるかを求めるプログラ ムを作成せよ.

입력

入力は以下の形式で標準入力から与えられる.

$N$ $K$

$S$

출력

標準出力に,葵が最小で何回操作を行う必要があるかを $1$ 行で出力せよ.

제한

  • $1 ≦ K ≦ N ≦ 200\,000$.
  • $S$ は ‘R’,‘G’,‘B’ からなる長さ $N$ の文字列である.
  • $N$, $K$ は整数である.

서브태스크

번호배점제한
110

$N ≦ 16$, $K = 1$.

226

$K = 1$.

326

$K ≦ 100$.

438

追加の制約はない.

예제 입력 1

8 1
BRGBRRGB

예제 출력 1

2

例えば以下のように $2$ 回の操作を行ったとき,点灯しているライトの色が “RGB” の繰り返しになる.消 灯しているライトを ‘-’ で表す.

  1. ライト $1$ を選び,消灯させる.それぞれのライトの状態は文字列 “-RGBRRGB” で表される.
  2. ライト $5$ を選び,消灯させる.それぞれのライトの状態は文字列 “-RGB-RGB” で表される.

$1$ 回以下の操作で点灯しているライトの色を “RGB” の繰り返しにすることはできないため,$2$ を出力する.

この入力例はすべての小課題の制約を満たす.

예제 입력 2

8 2
RGGGBBGR

예제 출력 2

3

例えば以下のように $3$ 回の操作を行ったとき,点灯しているライトの色が “RGB” の繰り返しになる.消 灯しているライトを ‘-’ で表す.

  1. ライト $2$, $3$ を選び,消灯させる.それぞれのライトの状態は文字列 “R--GBBGR” で表される.
  2. ライト $6$, $7$ を選び,消灯させる.それぞれのライトの状態は文字列 “R--GB--R” で表される.
  3. ライト $8$ を選び,消灯させる.それぞれのライトの状態は文字列 “R--GB---” で表される.

$2$ 回以下の操作で点灯しているライトの色を “RGB” の繰り返しにすることはできないため,$3$ を出力する.

この入力例は小課題 3, 4 の制約を満たす.

예제 입력 3

11 8
RGBBRGBBRGB

예제 출력 3

1

この入力例は小課題 3, 4 の制約を満たす.

예제 입력 4

10 3
RRRRRRRRRR

예제 출력 4

4

この入力例は小課題 3, 4 の制約を満たす.

예제 입력 5

6 1
RGBRGB

예제 출력 5

0

この入力例はすべての小課題の制約を満たす.

채점 및 기타 정보

  • 예제는 채점하지 않는다.