問題一覧 > 通常問題

No.1922 Separate and Attach

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 : 0214sh70214sh7
3 ProblemId : 8084 / 自分の提出
問題文最終更新日: 2022-05-01 23:54:55

問題文

$1, 2, \dots, N$ の順列 $P, Q$ が与えられます。 あなたは順列 $P$ に以下の操作をすることができます。

操作
  • $P$ から (連続とは限らない) 部分列を任意に取り出し、$S$ とおく。
  • $P$ の要素のうち $S$ に含まれない要素を $P$ の順番で結合したものを $T$ とおく。
  • $P$ を $S,T$ をこの順番で結合したもので置き換える。

あなたはこの操作を何回か繰り返すことで $P$ を $Q$ に一致させたいです。 最低で何回操作を行う必要がありますか?なお、この操作を有限回行うことで $P$ を $Q$ に一致させることができることが証明できます。


入力

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

$N$
$P_1$ $P_2$ $\cdots$ $P_N$ 
$Q_1$ $Q_2$ $\cdots$ $Q_N$  
  • $1 \le N \le 10^5$
  • $P,Q$ は長さ $N$ の順列
  • 入力は全て整数

出力

答えを出力せよ。

サンプル

サンプル1
入力
4
3 4 2 1
2 4 1 3
出力
2

以下の $2$ 回の操作により $(3,4,2,1)$ を $(2,4,1,3)$ と一致させることができます。

  • $P$ から部分列 $(4,1)$ を取り出し、残った $(3,2)$ と結合する。$P=(4,1,3,2)$ となる。
  • $P$ から部分列 $(2)$ を取り出し、残った $(4,1,3)$ と結合する。$P=(2,4,1,3)$ となる。

$1$ 回の操作では $P$ と $Q$ を一致させることができないため、$2$ を出力します。

サンプル2
入力
5
1 2 3 4 5
1 2 3 4 5
出力
0

最初から $P$ と $Q$ が一致していることもあります。

サンプル3
入力
15
4 6 8 9 15 7 12 2 1 11 10 14 5 3 13 
10 11 12 3 6 4 7 14 1 2 5 15 9 13 8
出力
4

出典

CPCTF22

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