E - Keep Being Substring Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

長さ N の整数列 A = (A_1, A_2, \ldots, A_N) が与えられます。 また、A の長さ P の連続な部分列 X = (X_1, X_2, \ldots, X_P) と、A の長さ Q の連続な部分列 Y = (Y_1, Y_2, \ldots, Y_Q) が与えられます。

X に対して、下記の 4 つのいずれかを行うという操作を、好きな回数（ 0 回でも良い）だけ行うことができます。

  • X の先頭に任意の整数を 1 つ追加する。
  • X の先頭の要素を削除する。
  • X の末尾に任意の整数を 1 つ追加する。
  • X の末尾の要素を削除する。

ただし、各操作の前後において、X は A の空でない連続な部分列でなければなりません。 X を Y と一致させるために行う操作回数の最小値を求めてください。 なお、本問題の制約下において、操作の繰り返しによって X と Y を必ず一致させられることが証明できます。

連続な部分列とは？

数列 X = (X_1, X_2, \ldots, X_P) が数列 A = (A_1, A_2, \ldots, A_N) の連続な部分列であるとは、1 \leq l \leq N-P+1 を満たす整数 l が存在して、 すべての i = 1, 2, \ldots, P について、X_i = A_{l+i-1} が成り立つことです。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq N
  • 1 \leq P, Q \leq N
  • (X_1, X_2, \ldots, X_P) と (Y_1, Y_2, \ldots, Y_Q) は、(A_1, A_2, \ldots, A_N) の連続な部分列
  • 入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N
P
X_1 X_2 \ldots X_P
Q
Y_1 Y_2 \ldots Y_Q

出力

答えを出力せよ。

入力例 1

7
3 1 4 1 5 7 2
2
3 1
3
1 5 7

出力例 1

3

下記の手順で操作すると、X が A の空でない連続な部分列であるという条件を満たしたまま、X を Y に一致させることが出来ます。

  1. まず、X の先頭の要素を削除する。その結果、X = (1) となる。
  2. 次に、X の末尾に 5 を追加する。その結果、X = (1, 5) となる。
  3. さらに、X の 末尾に 7 を追加する。その結果、X = (1, 5, 7) となり、X は Y と一致する。

上記の手順の操作回数は 3 回であり、これが考えられる最小の操作回数です。

入力例 2

20
2 5 1 2 7 7 4 5 3 7 7 4 5 5 5 4 6 5 6 1
6
1 2 7 7 4 5
7
7 4 5 5 5 4 6

出力例 2

7

Score : 700 points

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N) of length N. Additionally, its contiguous subsequences of lengths P and Q are given: X = (X_1, X_2, \ldots, X_P) and Y = (Y_1, Y_2, \ldots, Y_Q).

You can perform the four operations on X below any number of times (possibly zero) in any order.

  • Add an arbitrary integer at the beginning of X.
  • Delete the element at the beginning of X.
  • Add an arbitrary integer at the end of X.
  • Delete the element at the end of X.

Here, X must be a non-empty contiguous subsequence of A before and after each operation. Find the minimum total number of operations needed to make X equal Y. Under the Constraints of this problem, it is guaranteed that one can always make X equal Y by repeating operations.

What is a contiguous subsequence?

A sequence X = (X_1, X_2, \ldots, X_P) is a contiguous subsequence of A = (A_1, A_2, \ldots, A_N) when there is an integer l satisfying 1 \leq l \leq N-P+1 such that X_i = A_{l+i-1} for every i = 1, 2, \ldots, P.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq N
  • 1 \leq P, Q \leq N
  • (X_1, X_2, \ldots, X_P) and (Y_1, Y_2, \ldots, Y_Q) are contiguous subsequences of (A_1, A_2, \ldots, A_N).
  • All values in the input are integers.

Input

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

N
A_1 A_2 \ldots A_N
P
X_1 X_2 \ldots X_P
Q
Y_1 Y_2 \ldots Y_Q

Output

Print the answer.

Sample Input 1

7
3 1 4 1 5 7 2
2
3 1
3
1 5 7

Sample Output 1

3

You can make X equal Y while keeping X a non-empty contiguous subsequence of A, as follows.

  1. First, delete the element at the beginning of X. Now, you have X = (1).
  2. Next, add 5 at the end of X. Now, you have X = (1, 5).
  3. Furthermore, add 7 at the end of X. Now, you have X = (1, 5, 7), which equal Y.

Here, you perform three operations, which is the fewest possible.

Sample Input 2

20
2 5 1 2 7 7 4 5 3 7 7 4 5 5 5 4 6 5 6 1
6
1 2 7 7 4 5
7
7 4 5 5 5 4 6

Sample Output 2

7