問題一覧 > 通常問題

No.1115 二つの数列 / Two Sequences

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 240
作問者 : null / テスター : tyawanmusi
8 ProblemId : 3927 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-25 23:36:59

問題文

null くんは長さ nn の順列 P={1,2,…,n}P = \{1, 2, \dots, n\} を並べ替えた数列 A={a1,a2,…,an},B={b1,b2,…,bn}A = \{a_1, a_2, \dots, a_n\}, B= \{b_1, b_2, \dots, b_n\} を持っています。
null くんは以下の操作を繰り返して A=BA = B としたいです。

  • 1≤i≤n−11 \le i \le n - 1 を満たす整数 ii を一つ選び、aia_i と ai+1a_{i+1} を入れ替える。
A=BA = B とするのに必要な操作回数の最小値を求めてください。
ただし、1≤j≤n1 \le j \le n を満たすすべての jj について aj=bja_j = b_j が成り立つとき、A=BA=B とします。

入力

nn
a1 a2 …ana_1 \ a_2 \ \dots a_n
b1 b2 …bnb_1 \ b_2 \ \dots b_n

1≤n≤1051 \le n \le 10^5
A,BA, B は順列 PP を並べ替えた数列である。
入力はすべて整数である。

出力

A=BA = B とするのに必要な操作回数の最小値を一行に出力してください。 最後に改行してください。

サンプル

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

例えば、
1,5,4,2,3→1,5,2,4,3→1,2,5,4,3→2,1,5,4,3→2,1,4,5,3→2,1,4,3,51, 5, 4, 2, 3 \rightarrow 1, 5, 2, 4, 3 \rightarrow 1, 2, 5, 4, 3 \rightarrow 2, 1, 5, 4, 3 \rightarrow 2, 1, 4, 5, 3 \rightarrow 2, 1, 4, 3 ,5
と操作をすると操作回数は最小になり、これ未満の操作回数で条件を達する方法はありません。

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

最初から A=BA = B の場合もあります。

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

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

サンプル5
入力
26
21 13 12 24 4 7 20 1 10 8 22 14 3 16 9 11 15 5 19 18 23 2 17 6 25 26
17 3 18 7 8 14 5 15 1 12 11 13 2 4 22 9 21 19 24 16 20 6 25 26 10 23
出力
150

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