← 返回题目列表

AtCoder · utpc2024_n

N. 漂亮的花束

中文机器翻译题面 查看原题

配点 : 100 点

問題文

由进行花卉销售的 Universal Tropical Plant Center (UTPC) 公司拥有的农场,东西方向排列成一列 N 树木已经被种植,从西边开始依次是 1,2,\dots,N 。

在 UTPC 公司的农园里,从现在起K 进入为期 日的收获期。在收获期期间,每棵树每天都会开出红色、绿色或蓝色的花中的一种 1 只开花一朵。树 i 在今后 K 天内要开的花的颜色信息是字符串 S_i 什么时候可以工作j 关于第几天开花的颜色,S_i 可以得到第 j 文字目 S_{i,j} 是 在 R 的情况下为红色, 在 G 的情况下为绿色, 在 B 的情况下为蓝色。 在

UTPC 公司每天都会收获当天开放的所有花朵, 并将它们每3 朵装成一束花销售。这些花束必须保证,3 朵花要么全是同一种颜色,要么全是不同的颜色。 本来,我们希望每天收获的花朵不会剩下 1 朵,从而能够正好组成花束,但目前情况是,这种花束的制作方法不一定存在。因此,在收获期开始之前,我们决定可以将以下操作各自重复任意次数。 选择

  • 1 以上 N 的整数 给出了 i ,并砍掉树 i 。被砍的树将无法再收获花朵。 在
  • 1 以上 N 的整数 给出了 i ,并砍掉树 i 上施加促进剂。施加促进剂后,接下来的 K 天内, 将开 2 朵花。也就是说,j 当天 我计划睡 S_{i,j} 颜色的花 2 将会开出…。

另外,对于同一棵树 2 不能进行超过 次操作。而且,这个操作在进入收获期后无法进行。

由于 UTPC 公司的办公室位于农场的西端,因此尽量不想对种在东边的树进行操作。因此,一系列操作是通过成本 需要,被操作树中最东边的树的编号来定义的。不对任何树进行操作的成本是 0 。

在收获期间的任何一天,花都不会剩下 1 的操作方法中的最小成本。并且,如果砍掉所有树,认为花不会剩下 1 。

制約

  • N, K 是一个整数
  • 1 \leq N,K
  • NK \leq 10^5
  • |S_i|=K
  • S_i 的每个字符, R, G, B 是

入力

输入是按以下格式从标准输入给出的。

N K
S_1
S_2
\vdots
S_N

出力

答案 请打印除以 1 行输出。


入力例 1

4 5
RGBGR
BGGBR
RBGBR
RRRRR

出力例 1

2

2 砍掉第 树时,开花的颜色为

  • 1 第 日:RRR
  • 2 第 日:GBR
  • 3 第几天:BGR
  • 4 第 日:GBR
  • 5 第 日:RRR

于是,每一天都满足条件。在这种情况下的成本是 2 。 1 无法用成本


入力例 2

3 3
RGB
BGG
GGR

出力例 2

0

达成目标。


入力例 3

3 4
GGGG
BGGG
GGGR

出力例 3

3

不需要进行操作。


入力例 4

6 4
BGGB
BGGB
RGBG
RRRR
GGGG
BBBB

出力例 4

3

1 必须砍掉所有的树。3 砍掉第 树时,开花的颜色为

  • 1 给第几棵树施加生长剂,
  • 2 第几天:BBBRGB
  • 3 第几天:BBBRGB
  • 4 给第几棵树施加生长剂,

第几天:GGGRGB