G - At Most Two Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

長さ N の整数列 A, 及び長さ M の整数列 B が与えられます。

A, B の最長共通部分列 (LCS) の長さを求めてください。

なお、この問題においては以下のことが保証されます。

  • 任意の整数 x について、A_i=x なる i は高々 2 つしか存在しない。
最長共通部分列とは？

    ある 2 数列 x, y の最長共通部分列とは、x の部分列であってかつ y の部分列であるような数列 z のうち、長さが最大のもののことを指します。

    ここである数列 p の部分列とは、p から 0 個以上の要素を取り出し、それらを順序を変えずに並べた列のことを指します。

制約

  • 1 \leq N,M \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9\ (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^9\ (1 \leq i \leq M)
  • 任意の整数 x について、A_i=x なる i は高々 2 つまでしか存在しない
  • 入力は全て整数

入力

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

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

出力

A と B の最長共通部分列の長さを出力せよ。

入力例 1

3 3
1 2 2
2 1 2

出力例 1

2

(1,2), 或いは (2,2) が A と B の最長共通部分列です。

入力例 2

2 3
1 3
2 4 6

出力例 2

0

このように、A と B の最長共通部分列が空になる場合もあります。

入力例 3

6 5
3 1 5 3 1 4
10 4 9 10 2

出力例 3

1

原案: penguinman