kuretchi's blog

kuretchi's blog

競技プログラミングなどなど...

yukicoder - No.585 工夫のないパズル

https://yukicoder.me/problems/no/585

コンテスト中、A 問題を通した後ずっとこれを実装していて、結局間に合わず 1 完になった。でも ★4 AC は嬉しい。

概要

4 × 4 のスライドパズルを解く問題。いわゆる 15 パズル と似ているが、空きマスがない代わりに行か列を一つ選んでスライドすることができるというルール。右か下に任意マス分スライドするのを 1 回として、100 回以内の自由な操作で揃えればよい。

解説

おもむろに実験すると、最初の $3$ 行 (列でもいいけれど) は簡単にできそうということが分かる。後々の実装を楽にするために整理しておこう。

$i$ 行目 (0-indexed) までが揃っているとして ($0$ 行目は $-1$ 行目まで揃っていると考える)、次の $i + 1$ 行目を $i$ 行目までを崩さず揃えるには、基本的に下のようにすればよい。

今注目している移動させたい数字のマスの初期座標を $(sr, sc)$、移動先を $(tr, tc)$ とし (ただし、$(行, 列)$)、$round(i) = (i \% 4 + 4) \% 4$ とすると、

基本操作

  1. 列 $tc$ を $sr - tr$ 下へスライド
  2. 行 $sr$ を $round(tc - sc)$ 右へスライド
  3. 列 $tc$ を $4 - (sr - tr)$ 下へスライド

f:id:Kuretchi:20171028091512p:plain

ここでは、アルファベットの代わりに 0-15 の数字を使うことにする。今興味がない数字は省略。

ヤバそうなケースもしっかり考えておく。例えば、移動元と移動先が同じ行にある場合は、次のようにする。

移動元と移動先の行が同じ場合 ($sr = tr$)

  1. 列 $sc$ を $1$ 下へスライド
  2. 列 $tc$ を $1$ 下へスライド
  3. 行 $sr + 1 (= tr + 1)$ を $round(tc - sc)$ 右へスライド
  4. 列 $sc$ を $3$ 下へスライド
  5. 列 $tc$ を $3$ 下へスライド

f:id:Kuretchi:20171028091636p:plain

移動元と移動先が同じ列にある場合は、右へずらしてあげるとよい。

移動元と移動先の列が同じ場合 ($sc = tc$)

  1. 行 $sr$ を $1$ 右へスライド
  2. 基本操作 ($sc$ の値を更新しておくこと)

f:id:Kuretchi:20171028091700p:plain

以上の操作で、最初の $3$ 行を揃えることができる。

さて、最後の行を適当に入れ替えたい。簡単のために、隣り合うマスを交換する操作のみを考える。結論から言うと、次の操作で可能。

$r = sr (= tr)$、$c = round(sc + 1)$ とすると、

隣り合うマスの交換

  1. 列 $c$ を下へ $1$ スライド
  2. 行 $r$ を右へ $1$ スライド
  3. 列 $c$ を下へ $3$ スライド
  4. 行 $r$ を右へ $2$ スライド
  5. 列 $c$ を下へ $1$ スライド
  6. 行 $r$ を右へ $1$ スライド
  7. 列 $c$ を下へ $3$ スライド
  8. 行 $r$ を右へ $1$ スライド

f:id:Kuretchi:20171028132131p:plain

この操作によって、自明に列のマスを任意の順番に並べ替えることができるため、以上の考察ですべてのマスを揃えることができた。

ちなみに 適当にググって出てきたページ にも同じようなことが書いてある。

操作の回数については、以上の解法をそのまま実装すると少しギリギリだが、最適化の余地は十分にあるので、いい感じにえいすれば比較的余裕だと思われる。

実装例: C# / Haskell

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 + " ");
    }
}

ソートと要素のインデックス

ここらへんでハマってとてもつらかったので書いておきます。

ソート後のインデックスから、ソート前のインデックスを知りたい

f:id:Kuretchi:20170728115804p:plain:w600

方法1

インデックスとのペアのコレクションを作り、要素をキーとしてソートする。

char arr[5] = { 'D', 'A', 'C', 'E', 'B' };

pair<char, int> arridx[5];
for (int i = 0; i < 5; i++) arridx[i] = make_pair(arr[i], i);
// arridx => { (D, 0), (A, 1), (C, 2), (E, 3), (B, 4) }

sort(begin(arridx), end(arridx),
    [](pair<char, int>& a, pair<char, int>& b) {
        return a.first < b.first; });
// arridx => { (A, 1), (B, 4), (C, 2), (D, 0), (E, 3) }

方法2

インデックスだけのコレクションを作り、ソートしたいコレクションの対応する要素をキーとしてソートする。

char arr[5] = { 'D', 'A', 'C', 'E', 'B' };

int idx[5];
for (int i = 0; i < 5; i++) idx[i] = i;
// idx => { 0, 1, 2, 3, 4 }

sort(begin(idx), end(idx),
    [&arr](int& a, int& b) { return arr[a] < arr[b]; });
// idx => { 1, 4, 2, 0, 3 }

このソートされたインデックスを使って、ソートされた順番で要素にアクセスできる。

for (int i = 0; i < 5; i++) cout << arr[idx[i]] << " ";
// => "A B C D E "

ソート前のインデックスから、ソート後のインデックスを知りたい

f:id:Kuretchi:20170728115811p:plain:w600

コレクションが与えられた後、そのインデックスがクエリとして与えられるが、事前に元のコレクションをソートしておく必要がある場合など。上図では、例えば要素 D について、ソート前のインデックス 0 からソート後のインデックス 3 を得ることができる。

前述の、ソートされたインデックスのコレクションから生成する。

方法1

int after_idx[5];
for (int i = 0; i < 5; i++) after_idx[arridx[i].second] = i;
// after_idx => { 3, 0, 2, 4, 1 }

方法2

int after_idx[5];
for (int i = 0; i < 5; i++) after_idx[idx[i]] = i;
// after_idx => { 3, 0, 2, 4, 1 }