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

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

AtCoder AGC 001 F - Wide Swap (2000 点)

これも自力で解けたの、嬉しい!!!!!

問題へのリンク

問題概要

正の整数  N, K が与えられる。 1, 2, \dots, N からなる順列  P に対して、以下の操作を好きな回数だけ行ってできる順列のうち、辞書順最小のものを求めよ

  •  |i - j| \ge K かつ  |P_i - P_j| = 1 を満たす  i, j に対して、 P_i P_j を swap する

制約

  •  2 \le N \le 5 × 10^{5}
  •  1 \le K \le N-1

まずは逆順列を考えてみる

見るからに難しそう!!!そもそも本番正解者数 0 じゃん!!!
ただ、順列を見たらいくつか考えてみるべきことはある。とりあえず逆順列を考えてみるのがそのうちの 1 つ。そうすると驚くほど見通しの良い問題になってビックリした。

  • 順列  P (0-start で考える) に対して
  •  |P_{i} - P_{i+1}| \ge K を満たすならばここを隣接 swap ができる
  • そのような隣接 swap を好きな回数だけ行ってできる順列のうち、「 0 が理論上最も前に来るもの」のうち「 1 が理論上最も前に来るもの」のうち... なものを求めよ

という問題になる。ここまではルーティーン。そして、元の問題よりもずっと考えやすくなった気がする。隣接 swap 操作というのは色々なことができて

いろんなことが思い浮かぶ。

変換した問題をどう解くか: 僕は分割統治法

ではこの隣接 swap 問題をどう解くか。解説の方針を実はまだちゃんと理解していない...僕なりの方法を...!!!

方針としては Greedy そのもの。まずは  0 を極力前に持って行くことを最優先に考えて、その次に  1 を極力前に持って行くことを最優先に考えて...という感じ。

ここで、0 を前に持って行こうとすると、それ以上前に行けない壁にぶつかったりする。でもその時、その壁はもっと前に持っていけて、結果的に 0 もさらに前に持っていけたりする。それをずっと続けると「どの隣接する2要素についても前の要素が後ろの要素より  K 以上大きい、という部分は完全になくなる」という状態になる。ひっくり返せない場所もあるから、あたかも  N 要素の条件を反映したグラフの辞書順最小なトポロジカルソートを求めるような問題になるわけだ。

僕はこんな雰囲気の、この隣接 swap 問題が、バブルソートっぽいなという気持ちになった。バブルソート高速化といえば、分割統治法に基づくマージソート。この問題も分割統治法によって高速化できないだろうか。

なんか、すごくややこしくてメチャ頑張ったけど、なんとかできた。例えば  K = 3 として、

 0, 3, 5, 7, 1, 4, 2, 6

とかで、左 4 個と右 4 個が整列済みだとする。このとき、まず左 4 個と右 4 個については順序が崩れることはない (崩したら確実に悪化するため)。

そして、 1, 4, 2, 6 がそれぞれどこまで前まで行けるのかを調べる。このとき

  • 1 は 3 と 5 の間
  • 4 は 5 と 7 の間
  • 2 は 3 と 5 の間
  • 6 は 7 の後ろ

まで最高で前に進めることがわかる。しかしここで、4 と 2 の順序は入れ替えないので、2 は 4 の後ろにとどまることになる。

また、例えば  K = 2 で、10 を前に進めようとして前に 6 があったりする場合は、そこで止めた方がいいことが確定する。なぜなら、心配なのが、そこで 10 をもっと前に進めて 6 を追い越して一時的に答えを悪化させても、最終的にもっと良い解になりうるならよいが、そんなことはありえない (あるとしたら 6 より小さい数が 10 の後ろに控えていて、それがもっと前に行ける場合だが、そうだったらマージされた時点で初めからその数は 10 の前にいる)

という感じのマージ処理を  O(N\log{N}) でできるので、全体として  O(N(\log{N})^{2}) の計算量となった。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int N, K;
vector<int> P, Q;

void mergesort(vector<int> &a, int left, int right) {
    if (right - left <= 1) return;
    int mid = (left + right) / 2;
    mergesort(a, left, mid);
    mergesort(a, mid, right);

    vector<pair<int, int> > rs;
    for (int i = mid; i < right; ++i) rs.push_back({ a[i], i - mid });
    sort(rs.begin(), rs.end(), greater<pair<int,int> >());

    vector<int> pl(right - mid);
    int pointer = mid;
    for (auto pa : rs) {
        int val = pa.first;
        int id = pa.second;
        while (pointer > left && a[pointer - 1] >= val + K) --pointer;
        pl[id] = pointer;
    }
    vector<int> res;
    int last = left;
    for (int i = 0; i < pl.size(); ++i) {
        for (int j = last; j < pl[i]; ++j) {
            res.push_back(a[j]);
        }
        last = max(last, pl[i]);
        res.push_back(a[i + mid]);
    }
    for (int i = last; i < mid; ++i) res.push_back(a[i]);
    for (int i = 0; i < res.size(); ++i) a[i + left] = res[i];
}

int main() {
    cin >> N >> K;
    P.resize(N); Q.resize(N);
    for (int i = 0; i < N; ++i) cin >> P[i], --P[i];
    for (int i = 0; i < N; ++i) Q[P[i]] = i;
    mergesort(Q, 0, N);
    vector<int> res(N);
    for (int i = 0; i < N; ++i) res[Q[i]] = i;
    for (int i = 0; i < N; ++i) cout << res[i]+1 << endl;
}