/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
文字列の 美しさ を、その文字列のなかで同じ 2 文字が隣り合っている位置の個数として定義します。
例えば、00011 の美しさは 3 で、10101 の美しさは 0 です。
S_{n,m} を n 文字の 0 と m 文字の 1 からなる長さ n+m の文字列全体の集合とします。
s_1,s_2 \in S_{n,m} について、s_1,s_2 の 距離 d(s_1,s_2) を 「隣り合った 2 文字を入れ替える操作によって文字列 s_1 を文字列 s_2 に並び替えるのに必要な最小の操作回数」 と定義します。
また、s_1,s_2,s_3\in S_{n,m} について、s_2 が s_1 と s_3 の 間にある ことを、d(s_1,s_3)=d(s_1,s_2)+d(s_2,s_3) で定義します。
s,t\in S_{n,m} が与えられるので、s と t の間にある文字列の美しさの最大値を出力してください。
制約
- 2 \le n + m\le 3\times 10^5
- 0 \le n,m
- s,t は n 文字の
0と m 文字の1からなる長さ n+m の文字列
入力
入力は以下の形式で標準入力から与えられる。
n m s t
出力
s と t の間にある文字列の美しさの最大値を出力せよ。
入力例 1
2 3 10110 01101
出力例 1
2
10110 と 01101 の距離は 2 で、これらの間にある文字列は、10110, 01110, 01101, 10101 です。
それぞれの美しさは 1,2,1,0 であるため、答えは 2 です。
入力例 2
4 2 000011 110000
出力例 2
4
000011 と 110000 の距離は 8 です。
美しさが最大になる文字列は 000011 と 110000 で、答えは 4 です。
入力例 3
12 26 01110111101110111101001101111010110110 10011110111011011001111011111101001110
出力例 3
22
Score : 700 points
Problem Statement
Let us define the beauty of the string as the number of positions where two adjacent characters are the same.
For example, the beauty of 00011 is 3, and the beauty of 10101 is 0.
Let S_{n,m} be the set of all strings of length n+m formed of n 0s and m 1s.
For s_1,s_2 \in S_{n,m}, let us define the distance of s_1 and s_2, d(s_1,s_2), as the minimum number of swaps needed when rearranging the string s_1 to s_2 by swaps of two adjacent characters.
Additionally, for s_1,s_2,s_3\in S_{n,m}, s_2 is said to be between s_1 and s_3 when d(s_1,s_3)=d(s_1,s_2)+d(s_2,s_3).
Given s,t\in S_{n,m}, print the greatest beauty of a string between s and t.
Constraints
- 2 \le n + m\le 3\times 10^5
- 0 \le n,m
- Each of s and t is a string of length n+m formed of n
0s and m1s.
Input
Input is given from Standard Input in the following format:
n m s t
Output
Print the greatest beauty of a string between s and t.
Sample Input 1
2 3 10110 01101
Sample Output 1
2
Between 10110 and 01101, whose distance is 2, we have the following strings: 10110, 01110, 01101, 10101.
Their beauties are 1, 2, 1, 0, respectively, so the answer is 2.
Sample Input 2
4 2 000011 110000
Sample Output 2
4
Between 000011 and 110000, whose distance is 8, the strings with the greatest beauty are 000011 and 110000, so the answer is 4.
Sample Input 3
12 26 01110111101110111101001101111010110110 10011110111011011001111011111101001110
Sample Output 3
22