kuretchi's blog

競技プログラミング初心者のブログです。

AtCoder Regular Contest 080: E - Young Maids

http://arc080.contest.atcoder.jp/tasks/arc080_c

概要

ある正の偶数 $N$ について、 $(1,2,\cdots,N)$ の順列 $p=(p_1,p_2,\cdots,p_N)$ が与えられる。 $p$ のうち隣り合う $2$ 項を取り、新しい数列 $q$ の先頭に追加する。これを $p$ が空になるまで ($N/2$ 回) 繰り返したとき、 $q$ は $(1,2,\cdots,N)$ の順列になっているが、このような $q$ のうち辞書順最小のものを求めよ。

解法

$q$ の初項にできるだけ小さい数を持って来たい。サンプル 3 を見てみよう。

$p=(4,6,3,2,8,5,7,1), q=(3,1,2,7,4,6,8,5)$

$q$ の初項は $3$ となっているが、これは $p$ の偶数番目の項の最小値であり、その次の $1$ は、 $p$ で $3$ より後ろの項のうち奇数番目の項の最小値である。すなわち、任意の数列について、同様の議論によって前から 2 つの項が決定可能であることが分かる。

$3,1$ を除くと、 $p$ が分割され $(4,6),(2,8,5,7)$ の 2 つの数列ができる ($1$ が末項でなければ 3 つ)。あとは、先程の議論に従って、それぞれの数列に対して、前から 2 つの項を再帰的に決定していけばよい。この場合、 $(4,6)$ より $(2,8,5,7)$ からの方が辞書順で小さい 2 項を取ることができるので、先にこちらを処理する。これは、各数列の偶数番目の項の最小値を比較すればよい。

以上を愚直にやると $O(N ^ 2)$ となり間に合わないため、適切なデータ構造を使って高速化しよう。数列のある区間における偶数 (奇数) 番目の項の最小値は、Segment 木を 2 つ用意しておけば $O(\log N)$ で求められる (更新の必要がないため、Sparse Table 等を用いてもよい)。分割された数列のうち次に処理すべき数列を決めるには、毎回、偶数番目の項の最小値をキーとして、数列を優先度付きキューに enqueue することで、処理すべき順序で数列が得られる ($O(\log N)$)。以上の工夫で、全体の計算量は $O(N \log N)$ となり十分高速。

実装

偶数 (奇数) 番目の要素のみを格納した Segment 木を作ってもよいが、インデックスが面倒くさいことになるので、例えば偶数番目の要素のみの Segment 木は奇数番目に $\infty$ を入れておけばよい。

また、最小値を取り出すときに一緒にそのインデックスも得られるようにしておく必要がある。

static void Solve(IO io)
{
    var n = io.I;
    var p = io.Is(n);

    var pi = new int[n + 1];
    for (var i = 0; i < n; i++) pi[p[i]] = i;

    var evenp = p.Select((x, i) => i % 2 == 0 ? x : Inf).ToArray();
    var oddp = p.Select((x, i) => i % 2 != 0 ? x : Inf).ToArray();
    var evenst = new SegmentTree<int>(evenp, Inf, Min);
    var oddst = new SegmentTree<int>(oddp, Inf, Min);

    var xmin = Inf;
    var xmini = 0;
    var ymin = Inf;
    var ymini = n - 1;

    var pq = new PriorityQueue<Pair>();
    pq.Enqueue(new Pair(xmini, ymini, evenst[xmini, ymini]));

    while (pq.Any())
    {
        var pair = pq.Dequeue();

        xmin = pair.X % 2 == 0 ?
            evenst[pair.X, pair.Y] : oddst[pair.X, pair.Y];
        xmini = pi[xmin];
        ymin = pair.X % 2 == 0 ?
            oddst[xmini + 1, pair.Y] : evenst[xmini + 1, pair.Y];
        ymini = pi[ymin];

        if (xmini > pair.X)
        {
            var tl = pair.X;
            var tr = xmini - 1;
            var min = pair.X % 2 == 0 ? evenst[tl, tr] : oddst[tl, tr];

            pq.Enqueue(new Pair(tl, tr, min));
        }

        if (ymini - xmini > 1)
        {
            var tl = xmini + 1;
            var tr = ymini - 1;
            var min = pair.X % 2 == 0 ? oddst[tl, tr] : evenst[tl, tr];

            pq.Enqueue(new Pair(tl, tr, min));
        }

        if (ymini < pair.Y)
        {
            var tl = ymini + 1;
            var tr = pair.Y;
            var min = pair.X % 2 == 0 ? evenst[tl, tr] : oddst[tl, tr];

            pq.Enqueue(new Pair(tl, tr, min));
        }

        Write(xmin + " " + ymin + " ");
    }
}