問題一覧 > 通常問題

No.3782 Synchronized Subsequences

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 9
作問者 : askr58 / テスター : 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 13587 / 自分の提出
問題文最終更新日: 2026-10-26 08:33:57
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 520 (順位表) の他の問題:

Note

The time limit for this problem is $3$ seconds.

Problem Statement

You are given a positive integer $N$ and permutations $P=(P_1,P_2,\cdots,P_N)$ and $Q=(Q_1,Q_2,\cdots,Q_N)$ of $(1,2,\cdots ,N)$. Find the maximum integer $k$ such that there exists a pair of $2$ integer sequences of length $k$, $(A,B)=((A_1,A_2,\cdots ,A_k),(B_1,B_2,\cdots ,B_k))$, satisfying the following conditions. (It can be proved that at least one such pair $(A,B)$ exists.)

  • $A$ is a (not necessarily contiguous) subsequence of $P$, and $B$ is a (not necessarily contiguous) subsequence of $Q$.
  • For each integer $i$ satisfying $1\le i< k $, $(A_{i+1}-A_i)(B_{i+1}-B_i) > 0$.

Solve $T$ test cases.

Constraints

  • $1\le T\le 1000$
  • $1 \le N \le 1000$
  • $(P_1,P_2,\cdots ,P_N)$ and $(Q_1,Q_2,\cdots ,Q_N)$ are each a permutation of $(1,2,\cdots ,N)$
  • The sum of $N$ over the $T$ test cases is at most $1000$
  • All input values are integers

Input

The input is given in the following format, where $case_i$ denotes the $i$-th test case.

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

Each test case is given in the following format.

$N$
$P_1\ P_2\ \cdots\ P_N$
$Q_1\ Q_2\ \cdots\ Q_N$

Output

Print $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

Sample

Sample 1
Input
2
6
3 6 1 5 4 2
4 1 2 6 3 5
15
9 13 12 4 8 14 7 15 10 1 2 5 6 11 3
9 6 11 4 7 5 13 1 8 2 12 10 3 14 15
Output
4
11

For the $1$st test case, $A=(3,6,1,5),B=(4,6,3,5)$ satisfies the conditions. There is no $(A,B)$ of length $5$ or more satisfying the conditions, so the answer is $4$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。