実行時間制限: 2 sec / メモリ制限: 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 に一致させることが出来ます。
- まず、X の先頭の要素を削除する。その結果、X = (1) となる。
- 次に、X の末尾に 5 を追加する。その結果、X = (1, 5) となる。
- さらに、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.
- First, delete the element at the beginning of X. Now, you have X = (1).
- Next, add 5 at the end of X. Now, you have X = (1, 5).
- 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