[AGC019D] Shift and Flip
题意翻译
给你两个01串A和B,你可以进行以下3种操作:
1. 将A左移一位(如"0011" -> "0110")
2. 将A右移一位(如"0011" -> "1001")
3. 选择一个满足$B_i=1$的位置i,令$A_i=1-A_i$
问要使A和B相等至少要进行几次操作。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc019/tasks/agc019_d
$ 0 $ と $ 1 $ からなる同じ長さの二つの文字列 $ A\ =\ A_1\ A_2\ ...\ A_n $ と $ B\ =\ B_1\ B_2\ ...\ B_n $ があります。
あなたは、以下の操作を任意の順序で何度でも行って $ A $ を変化させることができます。
- $ A $ を一文字左にシフトする(すなわち、$ A\ =\ A_1\ A_2\ ...\ A_n $ として $ A $ を $ A_2\ A_3\ ...\ A_n\ A_1 $ に置き換える)。
- $ A $ を一文字右にシフトする(すなわち、$ A\ =\ A_1\ A_2\ ...\ A_n $ として $ A $ を $ A_n\ A_1\ A_2\ ...\ A_{n-1} $ に置き換える)。
- $ B_i\ =\ 1 $ であるような $ i $ をいずれか一つ選び、$ A_i $ を反転する(すなわち、$ A_i\ =\ 1\ -\ A_i $ とする)。
あなたの目標は文字列 $ A,\ B $ を一致させることです。
これに必要な最小の操作回数を出力してください。ただし、これが不可能である場合は $ -1 $ と出力してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ A $ $ B $
输出格式
文字列 $ A,\ B $ を一致させるために必要な最小の操作回数を出力せよ。ただし、これが不可能である場合は $ -1 $ と出力せよ。
输入输出样例
输入样例 #1
1010
1100
输出样例 #1
3
输入样例 #2
1
0
输出样例 #2
-1
输入样例 #3
11010
10001
输出样例 #3
4
输入样例 #4
0100100
1111111
输出样例 #4
5
说明
### 制約
- $ 1\ \leq\ |A|\ =\ |B|\ \leq\ 2,000 $
- $ A,\ B $ は $ 0 $ と $ 1 $ からなる。
### Sample Explanation 1
目標を達成する最短の操作列を一つ示します。 - $ A_1 $ を反転: $ A\ =\ 0010 $ - $ A $ を左にシフト: $ A\ =\ 0100 $ - $ A_1 $ を再度反転: $ A\ =\ 1100 $
### Sample Explanation 2
$ A $ の唯一のビットを反転させる方法はありません。
### Sample Explanation 3
目標を達成する最短の操作列を一つ示します。 - $ A $ を右にシフト: $ A\ =\ 01101 $ - $ A_5 $ を反転: $ A\ =\ 01100 $ - $ A $ を左にシフト: $ A\ =\ 11000 $ - $ A $ を再度左にシフト: $ A\ =\ 10001 $
### Sample Explanation 4
$ A_1 $, $ A_3 $, $ A_4 $, $ A_6 $, $ A_7 $ を任意の順序で反転すればよいです。