F - 白色光 (White Light) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

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

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

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

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

入力

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

N K
S

出力

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

制約

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

小課題

  1. (10 点) N \leqq 16,K = 1.
  2. (26 点) K = 1.
  3. (26 点) K \leqq 100.
  4. (38 点) 追加の制約はない.

入力例 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

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


Source Name

JOIG 2022/2023 春季トレーニング Contest Day2 問題2