ABC479 F - Narrow Passage
人が数直線上に立っていて、人 ははじめ座標 にいます。1 回の操作では、1 人を選んで座標 から か に動かします。移動先に人がいれば、その人は同時に座標 に移ります(2 人が入れ替わります)。
すべての人 が座標 にいる状態にするための操作回数の最小値を求める問題です(、、 はそれぞれ相異なり、 もそれぞれ相異なる)。
操作を 2 種類に分ける
Section titled “操作を 2 種類に分ける”1 回の操作は、次のどちらかです。
- 空いている座標への移動:1 人の座標が 変わります。人の並び順は変わりません。
- 隣の人との入れ替え:隣り合う 2 人の並び順が入れ替わります。2 人がいる座標の集合は変わりません。
人の並び順の変化は入れ替えでしか起こらないので、入れ替えの回数は、はじめと最後で前後関係が逆になっている 2 人の組の個数以上必要です。これは、人を の小さい順に並べ、それぞれの での順位を書いた列の転倒数です。
空いている座標への移動の回数を見積もるため、人 について
を考えます。座標がすべて 以上なら、 は座標 から人 の手前までにある空いている座標の個数です。
- 空いている座標へ移動すると、動いた人の がちょうど 変わり、ほかの人の は変わりません。
- 入れ替えでは、右に動いた人は座標が 増えて左にいる人数も 増え、左に動いた人はどちらも 減るので、2 人とも は変わりません。
の中で より小さいものの個数を 、 の中で より小さいものの個数を とすると、はじめの は 、最後の は です。したがって、空いている座標への移動は少なくとも 回必要です。
1 回の操作で減らせるのは、転倒数と のどちらか一方だけで、それも ずつです。したがって、答えは少なくとも
です。実はこの回数で必ず達成でき、これが答えになります。現在の状態で、上の値を 減らす操作が必ずあることを示します。以下、目標の を と書きます。左から並べたとき は広義単調増加で、2 人の が等しいのは座標が隣り合っているときです。 も目標の並び順で広義単調増加です。
- の人がいるとき:そのような人のうち最も右にいる人を とします。 の右隣の座標が空いていれば、 を右に動かすと が に 近づきます。右隣に人 がいるとき、 です。 は より右にいるので で、 です。目標では が並び順に広義単調増加なので、 は より左に来るはずです。 と を入れ替えると、転倒数が 減ります。
- の人だけがいるとき:左右を逆にして同様です。
- すべての人で のとき:転倒数が正なら、目標と前後が逆の隣り合う 2 人 (左)、(右)がいます。 かつ なので となり、2 人は座標が隣り合っています。入れ替えれば転倒数が 減ります。
と をそれぞれソートして順位を求め、転倒数を BIT などで数えれば、計算量は です。
Python
N = int(input())S = list(map(int, input().split()))T = list(map(int, input().split()))os = sorted(range(N), key=S.__getitem__)ot = sorted(range(N), key=T.__getitem__)rs = [0] * Nrt = [0] * Nfor k in range(N): rs[os[k]] = k rt[ot[k]] = kans = 0bit = [0] * (N + 1)for k, i in enumerate(os): x = rt[i] + 1 c = 0 while x > 0: c += bit[x] x -= x & -x ans += k - c x = rt[i] + 1 while x <= N: bit[x] += 1 x += x & -xfor i in range(N): ans += abs((T[i] - rt[i]) - (S[i] - rs[i]))print(ans)os は人を の小さい順に並べたもので、rs[i] は人 の での順位(0 始まり)、つまり より小さい の個数です。rt も同様に での順位です。
転倒数は、os の順に人を見ながら、それまでに見た人のうち での順位が人 より小さい人数 c を BIT で数え、k - c(順位が大きい人数)を足して求めています。最後に を足しています。
C++
#include "shogo-library/base/all"#include "shogo-library/others/inversion-number.hpp"#include "shogo-library/utility/vector_func.hpp"
void solve() { LL(N); VL(S, N); VL(T, N); vl rs = rank(S), rt = rank(T); ll ans = inversion_number(select(rt, argsort(S))); rep(i, N) ans += abs((T[i] - rt[i]) - (S[i] - rs[i])); print(ans);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}rank(S) は各要素の での順位(0 始まり)、argsort(S) は の小さい順に並べた添字の列です。select(rt, argsort(S)) で、人を の小さい順に並べたときの での順位の列を作り、inversion_number でその転倒数を求めています。inversion_number はマージソートで転倒数を数えます。
使用ライブラリ:cpp_include@6519da7