ARC088D
問題概要:
{0,1}からなる文字列Sが与えられる.連続した部分文字列の0/1を入れ替える作業をし,文字列Sを0のみになるようにしたい.この入れ替える区間の長さの最小値をKとするとき,Kの最大値を求めよ.
制約:
1 ≤ |S| ≤
解法:
まず連続する{0,1}の数を数える(連続した塊が左から数えてi番目であるとき,この数をとする).この数列の任意の区間を選んでマージして(下図)数列のサイズを1にするのが目的.
マージするときに選ぶ区間はできるだけ大きい方がいいので(Kを大きくするため),(全区間でない)最大の区間を選んでマージする,を繰り返すと最大のKが得られる.
最大の区間は{A}が負数を含まないため両端のうち小さい方を除く区間である.よってdequeを使って両端を比較することによって最大の区間を求めることはO(1)でできる.
赤枠の和の最小値(=4)が答え
