問題一覧 > 通常問題

No.1115 二つの数列 / Two Sequences

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 159
作問者 : nullnull / テスター : tyawanmusityawanmusi
6 ProblemId : 3927 / 出題時の順位表
問題文最終更新日: 2020-07-04 00:02:33

問題文

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

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

入力

$n$
$a_1 \ a_2 \ \dots a_n$
$b_1 \ b_2 \ \dots b_n$

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

出力

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

サンプル

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

例えば、
$1, 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 = 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もしくは右上の雲マークをクリックしてアカウントを作成してください。