ARC088 D : Wide Flip(500)
作成日：2017.12.31
最終更新日：2017.12.31
問題概要
文字$0$,$1$からなる文字列$S$に対して、操作「$S$中の長さ$K$以上の区間を選び、区間内の$0$と$1$を入れ替える」を行う。
操作を繰り返し行うことで$S$の要素をすべて$0$にできるような$|S|$以下の整数$K$の最大値を求めよ。
制約
$1 \leq |S| \leq 10^5$
考え方
区間に対する操作であるから、要素の差分を考える。
すなわち、$d_i$$= S_i$$\: xor \:$$S_{i+1}$とする。
この時、操作は「$i \geq K-1$に対して$d_i$の$0$と$1$を入れ替える」、「$i \leq N-K$に対して$d_i$の$0$と$1$を入れ替える」、「$j \geq K$に対して$d_i$と$d_{i+j}$の$0$と$1$を入れ替える」とのいずれかに言い換えられる。
このうち最後に挙げたものは$K$を小さくすることなく前の2つに置き換えることができるので以降では考えない。
条件を満たすにはまず$S_0$が$0$でなければならない。
もし初めに$S_0 = 1$であったならば$S$の全区間を選び操作を行えば良い。
これは$K \leq |S|$であることから、常に行うことができる。
後は$d_i$をすべて$0$にできれば良い。
$d_i$で初めから$0$のものに対しては操作を行う必要がない。
一方$d_i = 1$であるものに対しては操作を行う必要がある。
1つ目の操作は$K \leq i + 1$、2つ目の操作は$K \leq |S|-1-i$であれば行うことができる。
$K$を最大化するためには$i+1$$< |S| - 1 - i$なら前者、そうでないなら後者の操作をするのが良い。
この時、答えは$d_i$が$1$であるような$i$について$max(i+1$$,|S|-1-i)$の最小値である。
ソースコード
マクロ等はこちら
string S;
int main(){
cin >> S;
int N = S.size();
int ans = N;
repp(i,0,N-1) if(S[i] != S[i+1]) ans = min(ans,max(i+1,N-1-i));
cout << ans << endl;
return 0;
}解法まとめ
$S_i \neq S_{i+1}$である$i$について$max(i+1$$,|S|-1-i)$の最小値が答えである。
但し、そのような$i$が存在しなければ$|S|$が答えである。(5-8行)