第18回日本情報オリンピック　予選３

2018年12月10日
情報オリンピック日本委員会

解説

マルが 2 個連続，あるいはバツが 2 個連続している箇所は，その 2 個をまたいでスタンプを使うことができない． よって，与えられた文字列 S は，同じ文字が連続する箇所で分割して，分割されたそれぞれの文字列について問題を解けば良い．最終的な答えは，分割されたそれぞれの文字列の解の総和になる．

分割された文字列は，同じ文字が連続することがないので，マルとバツが交互に並んだ文字列になる．このような文字列の解は，文字列長を 2 で割った値を小数点以下切り捨てた値と一致する．これは左から順にマルバツスタンプを使っていくことを考えると容易にわかる．

例えば，"OOXOXOXOXOOOOXOXX" という文字列は
　　"O", "OXOXOXOXO", "O", "O", "OXOX", "X"
というふうに分割する．

それぞれの文字列について，文字列長を 2 で割った値を小数点以下切り捨てた値は
　　0, 4, 0, 0, 2, 0
となるので，総和の 6 が答えになる．

この操作を観察すると，文字列を実際に分割しなくても，先頭から順に，マルバツスタンプが使えるならば使う，使えないならば 1 文字のスタンプを使う，というふうに貪欲にスタンプを割り当てても解けることがわかる．この貪欲法を使えば O(Sの文字数) で解を求めることができる．