E - Keep Being Substring

Contest Duration: 2022-10-16(Sun) 12:00 - 2022-10-16(Sun) 14:00 (local time) (120 minutes) Back to Home

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$

出力

答えを出力せよ。

入力例 1Copy

Copy

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

出力例 1Copy

Copy

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

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

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

入力例 2Copy

Copy

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

出力例 2Copy

Copy

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 1Copy

Copy

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

Sample Output 1Copy

Copy

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 2Copy

Copy

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 2Copy

Copy