GCJ Qualification Round 2016 B. Revenge of the Pancakes

問題概要

+と-で構成された文字列 S が与えられる。左から k 番目までの順序を反転させ、かつその範囲の+と-を反転させる操作を繰り返しおこない、すべての文字を+にしたい。

操作回数の最小値を求めよ。

解法

貪欲に文字が変化する境目までを反転させればいい。

f:id:pekempey:20160410125638p:plain

どうしてうまくいくのかも考えてみよう。

まず、末尾の-を処理するには最低でも 1 回全体を反転しなければならないことが分かる。全体の反転はあまり意味がないので一番最後に使うことにしよう。

もう末尾の-は忘れてもいい。左から順にみたときの文字の種類の変化回数に着目すると、変化回数を 0 まで減らすには何回操作をする必要があるかという問題としても捉えられる。

文字が変化する境目までを反転させれば変化回数を 1 減らせる。一回の操作で変化回数を 2 以上減らすことはできない。

したがって境目までを反転させるのが最適になる。

GCJ Qualification Round 2016 B. Revenge of the Pan ...

順序の反転は関係なかった。