けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 048 C - Penguin Skating (黄色, 700 点)

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

問題概要

 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 に一致させるための最小回数を求めよ。

  •  a の 2 点  i \lt j を選ぶ
    • ただし、 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;
}