7K12 blog

猫でも分かるアルゴリズム解説

CPSCO2019 Session3 D - Decode RGB Sequence

f:id:tkr987:20200628024740p:plain

https://atcoder.jp/contests/cpsco2019-s3/submissions/9723196

  • 同じアルファベットが連続することからランレングス圧縮しておくと楽

f:id:tkr987:20200628024823p:plain

アルファベットが3文字しかないので、連続部分列をグループ化したときアルファベット遷移は2×3=6通りしかない。6通りの組み合わせについて有り得るかどうか考えていくと、R→G、G→RかB、B→RかG、の5通りは可能ということが分かる。

整理すると以下の条件が分かる。

  • 連続部分列RのあとにアルファベットBは来ない
  • 連続部分列Gの長さは必ず1文字
  • 左端はR、右端はBになる