たのしいたのしいたのしい家庭菜園(Growing Vegetables is Fun 3)

JOI 君は,長年にわたる家庭菜園の経験を生かして,自宅の庭で新たにジョイ草という植物を育ててい
る.庭には東西方向に並んだN 個のプランターがあり,西側から順に1 からN までの番号がついている.
ジョイ草は全部でN 株あり,それぞれのプランターに1 株ずつ植えてある.
春になって様子を見に行ったJOI 君は,ジョイ草が予想に反して色とりどりの葉を付けていることに気
がついた.さらに,ジョイ草が思ったほど生育していないことに気がついた.JOI 君はこれらのことを不
思議に思い,本で調べたところ,次のことがわかった:
• ジョイ草には3 種類あり,それぞれ赤,緑,黄の葉を付ける.
• 葉の色が同じジョイ草を近くに置くと,その成長が阻害されてしまう.
そこで,JOI 君は,ジョイ草を並び替えて,葉の色が同じジョイ草が隣り合わないようにすることにし
た.このとき,JOI 君は隣り合う2 つのジョイ草を入れ替えることしかできない.つまり,1 回の操作で
JOI 君はプランターi (1 ≦i ≦N −1) を任意に1 つ選び,プランターi のジョイ草とプランターi + 1 のジョ
イ草を入れ替えることができる.JOI 君は,できるだけ少ない回数の操作で,葉の色が同じジョイ草が隣
り合わないようにしたい.
ジョイ草の数と,それぞれのジョイ草の葉の色が与えられたとき,葉の色が同じジョイ草が隣り合わな
いように並び替えるために必要な操作回数の最小値を求めるプログラムを作成せよ.

• 1 ≦N ≦400.
• S は長さN の文字列である.
• S の各文字はR,G,Y のいずれかである.

1. (5 点) N ≦15.
2. (55 点) N ≦60.
3. (15 点) S の各文字はR,G のいずれかである.
4. (25 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.
N
S
S は長さN の文字列で,そのi 文字目(1 ≦i ≦N) は,プランターi に植えてあるジョイ草の葉の色が赤
ならばR,緑ならばG,黄ならばY である.

標準出力に,必要な操作回数の最小値を1 行で出力せよ.ただし,葉の色が同じジョイ草が隣り合わな
いように並び替えることが不可能ならば,代わりに−1 を出力せよ.

第18 回日本情報オリンピック(JOI 2018/2019) 本選
2019 年2 月10 日(茨城県つくば市)

생성자가 기록되지 않았습니다.

출처 JOI 2019 Final