想定解法とちょっと違うやり方したっぽい

問題概要

$L$ 個のマスが横一列に並んでいる ( $1, 2, \dots, L$ )。 $N$ 匹のペンギンがマス $A_{1} \le A_{2} \le \dots \le A_{N}$ にいる。

あなたは，次の操作を好きな回数行うことができる。

ペンギンを 1 匹選び、左または右へ向かって滑らせる
ペンギンは、目の前に空マスがある限り滑り続ける
別のペンギンのいるマスの直前のマスに到達する、もしくは目の前にマスが存在しなくなったら、ペンギンは停止する．

ペンギンの配置が $B_{1} \le B_{2} \le \dots \le B_{N}$ となるようにすることが可能かどうかを判定し、可能ならばそれを達成するための最小回数を求めよ。

制約

$1 \le N \le 10^{5}$
$N \le L \le 10^{9}$

考えたこと (僕の解法)

$i$ 番目のペンギンの位置に「 $-i$ する」という変換を行うと、ペンギンの動きは次のようにとらえられるようになる！

ペンギンを 1 匹選び、左または右へ向かって滑らせる
別のペンギンのいるマスか、マス 1 またはマス L に到達したら、ペンギンは停止する

つまり、ペンギンの直前のマスではなく、ペンギンのいるマスで止まる問題に帰着される。明らかに言えることとして、

$B$ の中に $A$ 中に含まれないものがあったら -1

$B$ の要素がすべて $A$ に含まれる場合には、 $A$ の座標を新たに 0, 1, ..., と番号を振り直すと、次のような問題に帰着される。

要素数も総和も等しい 2 つの配列 $a, b$ が与えられる。 $a$ に対して以下の操作を繰り返して、 $b$ に一致させるための最小回数を求めよ。

の 2 点を選ぶ
- ただし、 $a_{i+1}, \dots, a_{j-1}$ がすべて 0 である必要がある
そして以下のいずれかの操作を行う
- $a_{i}$ += 1、 $a_{j}$ -= 1 とする
- $a_{i}$ -= 1、 $a_{j}$ += 1 とする

この問題は左から順に揃えていく Greedy で解ける。 $b_{i} = 0$ となる箇所は例外的扱いをすることに注意する。

全体の計算量は $O(N \log N)$ となる。

結構大変なケース

以下のようなケースは結構厄介

9 100
2 3 5 7 9 11 12 13 14
2 3 4 5 7 9 11 13 14

この場合は

$a = (2, 1, 1, 1, 4)$
$b = (4, 1, 1, 1, 2)$

となる。実に 8 回の操作回数を要する。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, L;
    cin >> N >> L;
    deque<int> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) cin >> B[i];

    auto solve = [&]() -> long long {
        for (int i = 0; i < N; ++i) A[i] -= i+1, B[i] -= i+1;
        A.push_front(0), A.push_back(L-N);
        B.push_front(0), B.push_back(L-N);
        map<int, long long> maA, maB;
        for (auto v : A) maA[v]++;
        for (auto v : B) {
            maB[v]++;
            if (!maA.count(v)) return -1;
        }
        vector<long long> S, T;
        for (auto it : maA) {
            S.push_back(it.second);
            T.push_back(maB[it.first]);
        }
        long long res = 0, dif = 0;
        for (int i = 0; i < S.size(); ++i) {
            if (T[i] == 0) res += S[i];
            else res += abs(dif) + abs(dif+S[i]-T[i]);
            dif += S[i] - T[i];
        }
        return res/2;
    };
    cout << solve() << endl;
}