Mister雑記

競プロやります。

ARC080-E 「Young Maids」 (800)

atcoder.jp

概要

長さ N順列 \{p_i\}が与えられる。ここで Nは偶数である。

以下の操作を \{p_i\}が空になるまで繰り返すことで、長さ Nの順列 \{q_i\}を作る。

  •  \{p_i\}の隣り合う2要素を選ぶ。これを順に x, yとする。
  •  x, yをこの順を保ったまま \{q_i\}先頭に挿入する。

こうして得られる \{q_i\}で、辞書順最小のものを求めよ。

制約

  •  2 \leq N \leq 2 \times 10^5
  •  Nは偶数。
  •  1 \leq p_i \leq N
  •  p_i \neq p_j  (i \neq j)

考察

まず挿入されるのが \{q_i\}末尾ではないことに気づくのに30分くらいかかった1。ちゃんとサンプルを見よう。


辞書順最小なので、例によって貪欲で考える。今回は一番最後に選ぶペアの第一要素を最小にしたい。

一番最後に選べるペアについて考えると、この第一要素のindexは偶数(0-indexed)となることが分かる。 これは、それより前に並んでいる要素達はその中でペアを作らなければならないことから成り立つ。

indexが偶数の中での最小値のindexを lとしよう。 この相手も最小にしたいが、上と同様の理屈でペア間には偶数個の要素が入っていなくてはならない。 よって相手として選べる値は、indexが lより大きく奇数のものである。このindexを rとしよう。


こうして (p_l, p_r)というペアが先頭に来ることが分かった。 残りのペアは既に削除された要素を跨いではならないので、残りのペアは l, rによって分割された3つの区間から作らなければならない。

こうして分割した3つの区間に対しても、上と全く同じようにして最小のペアが求められる。 ここから私は「各区間の解を再帰的に求め、それらを貪欲にマージする」という手法を選んだ。 しかしこの解法は O(N^2)でTLEになってしまい、後一歩届かずとなった。

Editorial解法は「取れるペアが最も小さい区間を選び、その区間を分割してどんどん区間を増やす」という何ともダイナミックなものだった。 「区間をそのまま管理する」という発想がなぜ出なかったのか...

実装例

実装は実装で普通に重い。本来はセグ木のVerifyが目的だったのに、思いがけず返り討ちに遭ってしまった。

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

using namespace std;

const int INF = 1 << 30;

template <class Type>
class Segtree {
public:
    explicit Segtree(int N, Type e) : length(1), e(e) {
        while (length < N) length *= 2;
        nodes.assign(length * 2, e);
    }

    Type query(int ql, int qr, int nidx, int nl, int nr) {
        if (nr <= ql || qr <= nl) return e;
        if (ql <= nl && nr <= qr) return nodes[nidx];
        Type lval = query(ql, qr, nidx * 2, nl, (nl + nr) / 2);
        Type rval = query(ql, qr, nidx * 2 + 1, (nl + nr) / 2, nr);
        return min(lval, rval);
    }

    // half-open interval [ql, qr)
    Type query(int ql, int qr) {
        return query(ql, qr, 1, 0, length);
    }

    void update(int idx, Type val) {
        int nidx = idx + length;
        nodes[nidx] = val;
        while (nidx > 0) {
            nidx /= 2;
            nodes[nidx] = min(nodes[nidx * 2], nodes[nidx * 2 + 1]);
        }
    }

    int length;
    vector<Type> nodes;
    Type e;
};

int main() {
    int N;
    cin >> N;

    vector<Segtree<int>> seg(2, Segtree<int>(N, INF));
    // seg[i] = indexを2で割った余りがiであるものだけを集めたもの
    int p[N], rev[N];
    for (int i = 0; i < N; ++i) {
        cin >> p[i];
        --p[i];
        seg[i % 2].update(i, p[i]);
        rev[p[i]] = i;
    }

    vector<int> ans;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> que;
    que.push(make_tuple(seg[0].query(0, N), 0, N));
    // (区間[l, r)で選べる最小値, l, r)

    while (!que.empty()) {
        int mi, l, r;
        tie(mi, l, r) = que.top();
        que.pop();
        ans.push_back(mi);
        int d1 = rev[mi];

        // もう一方はd1で切った後ろにおける同様の最小値
        mi = seg[(d1 + 1) % 2].query(d1 + 1, r);
        ans.push_back(mi);
        int d2 = rev[mi];

        // 分割後の半開区間
        pair<int, int> segs[3] = {{l, d1}, {d1 + 1, d2}, {d2 + 1, r}};

        for (int i = 0; i < 3; ++i) {
            tie(l, r) = segs[i];
            if (l < r) que.push(make_tuple(seg[l % 2].query(l, r), l, r));
        }
    }

    for (int a : ans) cout << a + 1 << " ";
    cout << endl;
    return 0;
}

感想

  • 2回目なのに大体同じ場所で詰まってしまったのは要反省。
    • 冒頭の誤読も2回目。
  • ちなみにセグ木は内部ノードの管理を1-indexedにした。

  1. 末尾でもそれなりの問題になると思うが、実装が重いだけになりそうでもある。