A - Larger Score

一応、考察した内容ですが、あまり自信はないです。

$K$ 番目までの $A$ から順番を保ったまま抜き出した部分列を $x=\{x_1,\cdots , x_m\}$ 、同様に $K+1$ 番目以降の要素から得られる部分列を $y=\{y_1,\cdots , y_m\}$ とします。

また、任意の $x_i$ を $K+1$ 番目以降に移動させ、任意の $y_j$ を $K$ 番目以内に移動させる操作を入れ替えと呼ぶことにします。

入れ替えに必要な操作回数

$x_i$ と $y_j$ の入れ替えに必要な最小の操作回数は、 $x_i$ を $K$ 番目に移動させた後、 $y_j$ を $K$ 番目に移動させればよいので、 $x_i$ が $A_s$ 、 $y_j$ が $A_t$ とすると、 $K-s+t-K=t-s$ 回となります。

複数個入れ替える場合に必要な操作回数

例えば、 $i'\lt i$ である $x_{i'},x_i$ と、 $j\lt j'$ である $y_j , y_{j'}$ を入れ替える場合を考えます。
この時、 $x_i$ と $y_j$ を入れ替えてから、 $x_{i'}$ と $y_{j'}$ を入れ替える必要があります。つまり、 $K$ 番目に近いもの同士から順に入れ替えます。

そうでない場合、操作回数はこれより増えます。
なぜなら、例えば、 $x_{i'}$ を先に $K$ 番目に移動させると、 $x_i$ は1つ前に出るため、必要な操作回数が1回増えます。

問題の条件を満たすのに必要な操作回数

まず、明らかに $x_i \lt y_j$ を満たすもの1組を入れ替えると達成可能です。

では、複数個入れ替えて最適になる場合があるか考えます。
今、 $K$ 以下と $K+1$ 以上から $m$ 個選び、それらが、以下の条件を満たすとします。

$x_1+\cdots +x_m \lt y_1+\cdots +y_m$

ここで、 $x_i \geq y_j$ となる組を取り除いても、条件は満たされます。

取り除けるだけ取り除くと、結局、任意の $x_i$ 、 $y_j$ について $x_i \lt y_j$ が成立します。

取り除いた後の個数を $m'$ すると、前述したとおり、 $x_{m'},x_{m'-1},\cdots , 1$ と $y_1,y_2,\cdots ,y_{m'}$ を順に入れ替えしていくのが最適です。
ここで、 $x_{m'}$ と $y_1$ を交換した時点で問題文の条件を満たすので、結局1個だけの交換を考慮するだけでよくなります。