2019-04-06

AtCoder AGC 001 F - Wide Swap (2000 点)

AtCoder AtCoder2000～点 AGC-F 順列を題材とした問題操作:隣接swap 操作:swap 操作順列テク:逆順列を考える条件の言い換え変数変換して扱いやすい同型な問題を見出す分割統治法辞書順最適化テク:探索候補を絞るグラフグラフの辺数を削減するトポロジカルソート priority_queue Greedy 天才のGreedy 可視化テク:二次元平面上に可視化する主客転倒ソートすることが目的の操作の問題操作後の結果の最適化問題思わず解きたくなる興味深い良問難しいGreedy

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

問題へのリンク

問題概要

正の整数 $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 操作というのは色々なことができて

DP するとか
バブルソートっぽいなとか

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

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

ではこの隣接 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;
}