E - Swap 0^X and 1^Y 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 900 点

問題文

0 と 1 のみからなる長さ N の文字列 S, T と、正整数 X, Y が与えられます。 i = 1, 2, \ldots, N について、S の i 文字目を S_i で表します。

「下記の操作 A と操作 B のどちらかを行う」ことを好きな回数（ 0 回でも良い）だけ繰り返すことで、S を T に一致させることができるかどうかを判定してください。

  • （操作 A）1 \leq i \leq N-(X+Y)+1, S_{i} = S_{i+1} = \cdots = S_{i+X-1} = 0, S_{i+X} = S_{i+X+1} = \cdots = S_{i+X+Y-1} = 1 を満たす整数 i を選び、S_{i}, S_{i+1}, \ldots, S_{i+Y-1} をそれぞれ 1 に、S_{i+Y}, S_{i+Y+1}, \ldots, S_{i+Y+X-1} をそれぞれ 0 に変更する。

  • （操作 B）1 \leq i \leq N-(X+Y)+1, S_{i} = S_{i+1} = \cdots = S_{i+Y-1} = 1, S_{i+Y} = S_{i+Y+1} = \cdots = S_{i+Y+X-1} = 0 を満たす整数 i を選び、S_{i}, S_{i+1}, \ldots, S_{i+X-1} をそれぞれ 0 に、S_{i+X}, S_{i+X+1}, \ldots, S_{i+X+Y-1} をそれぞれ 1 に変更する。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq X, Y \leq N
  • S, T はそれぞれ 0 と 1 のみからなる長さ N の文字列
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N X Y
S
T

出力

S を T に一致させることが可能な場合は Yes を、そうでない場合は No を出力せよ。

入力例 1

9 2 1
000111001
011000011

出力例 1

Yes

下記の手順によって S を T に一致させることができます。

  • まず、i = 2 として操作 A を行う。その結果、S = 010011001 となる。
  • 次に、i = 6 として操作 B を行う。その結果、S = 010010011 となる。
  • 最後に、i = 3 として操作 A を行う。その結果、S = 011000011 となる。

よって、Yes を出力します。

入力例 2

1 1 1
0
1

出力例 2

No

S を T に一致させることはできません。よって、No を出力します。

Score : 900 points

Problem Statement

You are given two strings S and T, each of length N and consisting of 0 and 1, as well as two positive integers X and Y. For i = 1, 2, \ldots, N, let S_i denote the i-th character of S.

Determine whether it is possible to make S identical to T by repeatedly performing Operations A and B below any number of times (possibly zero) in any order:

  • (Operation A) Choose an integer i satisfying 1 \leq i \leq N-(X+Y)+1, S_{i} = S_{i+1} = \cdots = S_{i+X-1} = 0, and S_{i+X} = S_{i+X+1} = \cdots = S_{i+X+Y-1} = 1, then change each of S_{i}, S_{i+1}, \ldots, S_{i+Y-1} to 1 and each of S_{i+Y}, S_{i+Y+1}, \ldots, S_{i+Y+X-1} to 0.

  • (Operation B) Choose an integer i satisfying 1 \leq i \leq N-(X+Y)+1, S_{i} = S_{i+1} = \cdots = S_{i+Y-1} = 1, and S_{i+Y} = S_{i+Y+1} = \cdots = S_{i+Y+X-1} = 0, then change each of S_{i}, S_{i+1}, \ldots, S_{i+X-1} to 0 and each of S_{i+X}, S_{i+X+1}, \ldots, S_{i+X+Y-1} to 1.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq X, Y \leq N
  • S and T are strings of length N consisting of 0 and 1.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N X Y
S
T

Output

If it is possible to make S identical to T, print Yes; otherwise, print No.

Sample Input 1

9 2 1
000111001
011000011

Sample Output 1

Yes

The following procedure can transform S into T:

  • First, perform Operation A with i = 2. Now, S = 010011001.
  • Next, perform Operation B with i = 6. Now, S = 010010011.
  • Finally, perform Operation A with i = 3. Now, S = 011000011.

Thus, print Yes.

Sample Input 2

1 1 1
0
1

Sample Output 2

No

It is impossible to make S identical to T. Thus, print No.