競技プログラミング用 知識集積所
ABC426D - Pop and Insert
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
考察問題。
一度も触らずに済む文字群は、最初から目的の文字になっているものだけの連続区間でなければならない。
例えば'0'に統一するとして、m個の0、n個の1、触らない'0'の長さがlであったとする。
すると、m-l個の0は2回ずつ（1度目で'1'になるので、戻すためにもう1回必要）、n個の1は1回ずつ触らなければならないので、操作回数は2*(m-l)+n回以上必要。
そして、1文字ずつ'0'にしていくときに、触らない区間に混ぜ込む位置に入れることとすれば、実際にこの回数で可能である。
よって、lは大きければ大きい方がよく、'0'に統一する場合は最も長く'0'が続く区間を触らない区間に選べばよい。
例えば'0'に統一するとして、m個の0、n個の1、触らない'0'の長さがlであったとする。
すると、m-l個の0は2回ずつ（1度目で'1'になるので、戻すためにもう1回必要）、n個の1は1回ずつ触らなければならないので、操作回数は2*(m-l)+n回以上必要。
そして、1文字ずつ'0'にしていくときに、触らない区間に混ぜ込む位置に入れることとすれば、実際にこの回数で可能である。
よって、lは大きければ大きい方がよく、'0'に統一する場合は最も長く'0'が続く区間を触らない区間に選べばよい。
'1'に統一する場合も同様の計算で済む。
それぞれを求め、小さい方を答えればよい。
それぞれを求め、小さい方を答えればよい。
