コンテンツにスキップ

ABC479 F - Narrow Passage

サイト
AtCoder
コンテスト
ABC479
問題
F - Narrow Passage
難易度
-

NN 人が数直線上に立っていて、人 ii ははじめ座標 SiS_i にいます。1 回の操作では、1 人を選んで座標 xx から x−1x - 1 か x+1x + 1 に動かします。移動先に人がいれば、その人は同時に座標 xx に移ります(2 人が入れ替わります)。

すべての人 ii が座標 TiT_i にいる状態にするための操作回数の最小値を求める問題です(1≤N≤2×1051 \le N \le 2 \times 10^5、0≤Si,Ti≤1090 \le S_i, T_i \le 10^9、SiS_i はそれぞれ相異なり、TiT_i もそれぞれ相異なる)。

1 回の操作は、次のどちらかです。

  • 空いている座標への移動:1 人の座標が 11 変わります。人の並び順は変わりません。
  • 隣の人との入れ替え:隣り合う 2 人の並び順が入れ替わります。2 人がいる座標の集合は変わりません。

人の並び順の変化は入れ替えでしか起こらないので、入れ替えの回数は、はじめと最後で前後関係が逆になっている 2 人の組の個数以上必要です。これは、人を SiS_i の小さい順に並べ、それぞれの TT での順位を書いた列の転倒数です。

空いている座標への移動の回数を見積もるため、人 ii について

ui=(人 i の座標)−(人 i より左にいる人数)u_i = (\text{人 } i \text{ の座標}) - (\text{人 } i \text{ より左にいる人数})

を考えます。座標がすべて 00 以上なら、uiu_i は座標 00 から人 ii の手前までにある空いている座標の個数です。

  • 空いている座標へ移動すると、動いた人の uiu_i がちょうど 11 変わり、ほかの人の uu は変わりません。
  • 入れ替えでは、右に動いた人は座標が 11 増えて左にいる人数も 11 増え、左に動いた人はどちらも 11 減るので、2 人とも uu は変わりません。

SS の中で SiS_i より小さいものの個数を rir_i、TT の中で TiT_i より小さいものの個数を ri′r'_i とすると、はじめの uiu_i は Si−riS_i - r_i、最後の uiu_i は Ti−ri′T_i - r'_i です。したがって、空いている座標への移動は少なくとも ∑i∣最後の ui−はじめの ui∣\sum_i |\text{最後の } u_i - \text{はじめの } u_i| 回必要です。

1 回の操作で減らせるのは、転倒数と ∑i∣ui の差∣\sum_i |u_i \text{ の差}| のどちらか一方だけで、それも 11 ずつです。したがって、答えは少なくとも

(転倒数)+∑i∣最後の ui−はじめの ui∣(\text{転倒数}) + \sum_i |\text{最後の } u_i - \text{はじめの } u_i|

です。実はこの回数で必ず達成でき、これが答えになります。現在の状態で、上の値を 11 減らす操作が必ずあることを示します。以下、目標の uiu_i を ui′u'_i と書きます。左から並べたとき uu は広義単調増加で、2 人の uu が等しいのは座標が隣り合っているときです。u′u' も目標の並び順で広義単調増加です。

  • ui<ui′u_i < u'_i の人がいるとき:そのような人のうち最も右にいる人を ii とします。ii の右隣の座標が空いていれば、ii を右に動かすと uiu_i が ui′u'_i に 11 近づきます。右隣に人 jj がいるとき、uj=uiu_j = u_i です。jj は ii より右にいるので uj≥uj′u_j \ge u'_j で、uj′≤uj=ui<ui′u'_j \le u_j = u_i < u'_i です。目標では u′u' が並び順に広義単調増加なので、jj は ii より左に来るはずです。ii と jj を入れ替えると、転倒数が 11 減ります。
  • ui>ui′u_i > u'_i の人だけがいるとき:左右を逆にして同様です。
  • すべての人で ui=ui′u_i = u'_i のとき:転倒数が正なら、目標と前後が逆の隣り合う 2 人 ii(左)、jj(右)がいます。ui≤uju_i \le u_j かつ uj′≤ui′u'_j \le u'_i なので ui=uju_i = u_j となり、2 人は座標が隣り合っています。入れ替えれば転倒数が 11 減ります。

SS と TT をそれぞれソートして順位を求め、転倒数を BIT などで数えれば、計算量は O(Nlog⁡N)O(N \log N) です。

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] * N
rt = [0] * N
for k in range(N):
rs[os[k]] = k
rt[ot[k]] = k
ans = 0
bit = [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 & -x
for i in range(N):
ans += abs((T[i] - rt[i]) - (S[i] - rs[i]))
print(ans)

os は人を SiS_i の小さい順に並べたもので、rs[i] は人 ii の SS での順位(0 始まり)、つまり SiS_i より小さい SS の個数です。rt も同様に TT での順位です。

転倒数は、os の順に人を見ながら、それまでに見た人のうち TT での順位が人 ii より小さい人数 c を BIT で数え、k - c(順位が大きい人数)を足して求めています。最後に ∣ui′−ui∣|u'_i - u_i| を足しています。

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) は各要素の SS での順位(0 始まり)、argsort(S) は SS の小さい順に並べた添字の列です。select(rt, argsort(S)) で、人を SS の小さい順に並べたときの TT での順位の列を作り、inversion_number でその転倒数を求めています。inversion_number はマージソートで転倒数を数えます。

使用ライブラリ:cpp_include@6519da7