SRM 551 Div2 Medium ColorfulChocolates

問題

異なる色のチョコが一列に並んでいる時,隣り合うチョコを入れ替える作業をk回繰り返してできるだけ同じ色が連続するように並び替えたい.

同じ色が連続する最大の個数を求める問題

解答

すべての色について,連続する位置の中心を決めたとき,最適な解はその中心に向かって,もっとも近い同じ色のチョコをグリーディーに求めることで得られる.

 

gistf7dcf386e48e87604546