AT_arc132_d [ARC132D] Between Two Binary Strings

[problemUrl]: https://atcoder.jp/contests/arc132/tasks/arc132_d 文字列の **美しさ** を、その文字列のなかで同じ $ 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 $ の間にある文字列の美しさの最大値を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ m $ $ s $ $ t $

$ s $ と $ t $ の間にある文字列の美しさの最大値を出力せよ。

### 制約 - $ 2\ \le\ n\ +\ m\le\ 3\times\ 10^5 $ - $ 0\ \le\ n,m $ - $ s,t $ は $ n $ 文字の `0` と $ m $ 文字の `1` からなる長さ $ n+m $ の文字列 ### Sample Explanation 1 `10110` と `01101` の距離は $ 2 $ で、これらの間にある文字列は、`10110`, `01110`, `01101`, `10101` です。 それぞれの美しさは $ 1,2,1,0 $ であるため、答えは $ 2 $ です。 ### Sample Explanation 2 `000011` と `110000` の距離は $ 8 $ です。 美しさが最大になる文字列は `000011` と `110000` で、答えは $ 4 $ です。