| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 15 | 9 | 7 | 63.636% |
$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ドル$ 行で出力せよ.
R’,‘G’,‘B’ からなる長さ $N$ の文字列である.| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N ≦ 16,ドル $K = 1$. |
| 2 | 26 | $K = 1$. |
| 3 | 26 | $K ≦ 100$. |
| 4 | 38 | 追加の制約はない. |
8 1 BRGBRRGB
2
例えば以下のように 2ドル$ 回の操作を行ったとき,点灯しているライトの色が “RGB” の繰り返しになる.消 灯しているライトを ‘-’ で表す.
-RGBRRGB” で表される.-RGB-RGB” で表される.1ドル$ 回以下の操作で点灯しているライトの色を “RGB” の繰り返しにすることはできないため,2ドル$ を出力する.
この入力例はすべての小課題の制約を満たす.
8 2 RGGGBBGR
3
例えば以下のように 3ドル$ 回の操作を行ったとき,点灯しているライトの色が “RGB” の繰り返しになる.消 灯しているライトを ‘-’ で表す.
R--GBBGR” で表される.R--GB--R” で表される.R--GB---” で表される.2ドル$ 回以下の操作で点灯しているライトの色を “RGB” の繰り返しにすることはできないため,3ドル$ を出力する.
この入力例は小課題 3, 4 の制約を満たす.
11 8 RGBBRGBBRGB
1
この入力例は小課題 3, 4 の制約を満たす.
10 3 RRRRRRRRRR
4
この入力例は小課題 3, 4 の制約を満たす.
6 1 RGBRGB
0
この入力例はすべての小課題の制約を満たす.