問題

問題概要

ハノイの塔のような、いくつかの棒と、それに積み重なった輪っかを考える。

棒は6行、6列の36本の棒が立っている(上から $r$ 行目、左から $c$ 行目の列の棒を棒 $(r,c)$ と呼ぶことにする)。輪っかは全部で $n$ 個あり、大きさはすべて異なる。輪っかには小さい方から順に1,2,3,...,nと番号をつける。

次のようなパズルを考える：

はじめ、 $n$ 個の輪っかは棒 $(1,1)$ に任意の順番で積み重なっている(下から $i$ 番目には輪っか $d_i$ がある)。これらを棒 $(6,6)$ に大きさがソートされた状態(大きいのが一番下、小さいのが一番上、つまり上から1,2,3,...,nの順)になるように移動させたい。1回の操作で出来るのは、ある棒を選び、上から $k$ 個をとりだして、そのまま下の棒か右の棒に移動する(棒 $(i,j)$ からは棒 $(i+1,j)$ または棒 $(i,j+1)$ に移動できる)ということである。

$n$ とはじめの状態 $d$ が与えられるので、このパズルを解く操作列を出力せよ。解は存在すると仮定して良い。

$1 \le n \le 40000$
$1 \le d_i \le n$
$d_i$ はすべて異なる(つまり順列)

アイデア

簡単な例を考えてみる。 $n$ が少なかったらどうかを考えてみると、4*4の棒があったときに、15個の輪っかを運びたいとする。

f:id:imulan:20181019054312p:plain

そして、空いている15マスのところに1箇所ずつ輪っかを運ぶ場所を指定して、(手間ですが)山の上から順番に1つずつ指定された場所に運ぶ。

f:id:imulan:20181019054542p:plain

あとは、これをいい感じの順番に右下に回収していけばソート完了になるのが想像できる。

ということで、こんな感じで棒がいっぱいあればソートは出来ることがわかる。ただ、1つの棒を1つの輪っか専用にするのが明らかに無駄な感じがする。

そこで、次のように同じ場所を2つの輪っかで共有するような方法を考えてみる。今度は輪っかが22個ある。

f:id:imulan:20181019055137p:plain

そして、ごちゃごちゃのままではあるが、この山を輪っかの大小を基準に小さい方を右へ、大きい方を下へ運ぶ。

f:id:imulan:20181019055338p:plain

2つの山に分けたあとに先程のような割当てを行い、順番に回収していくことを考える。

f:id:imulan:20181019055606p:plain

そうすると、2つの輪っかに割り当てられるマスが発生して、先程より効率よく使えていることがわかる。この方法に限って言えば、青い山の方を先に処理して、12から22を先に右下に集めてしまえば、赤い山は青い山に影響されることなくソートを行うことが出来る事がわかる。

このように、操作の前に既に下に何かあったとしても、その上の処理が終わるまでは一旦床とみなしてしまうことができ、その先の処理に何も影響がなさそうだ、ということが想像できる。

あとは、この例のような分配を再帰的に行ってソートをすることを考えたい。そこで、今回 $n$ の上限が40000なので、6*6マスで実現できるかを確かめよう。そこで $f(R,C)$ を残り $R$ 行 $C$ 列残っているときに、任意の並びの山をソート済みにできる最大の個数とすると、

再帰的に右下全部のマスで処理させることを考えると、処理可能な個数は $\displaystyle f(R,C) = \sum_{r \le R, c \le C, (r,c) \neq (R,C)} f(r,c)$ である。初期値は $f(1,1) = 1$ で計算すると、 $f$ の値は以下のテーブルの通りになる。

f:id:imulan:20181019060706p:plain

これでは、40000個を処理できない。もう少し工夫することを考える。

そこで、 $f(1,2) = 1$ となっていることに注目すると、これはもっと良くなる。具体的には、2にできる。なぜなら、2個ということはソート済みか、ひっくり返ってるかのどちらかしか無いが、ソート済みならそのまま一気に2個運んでしまえば良いし、ひっくり返ってるなら1個ずつ移動させればソート済みにできる。

ということで、新たに初期値 $f(1,1) = 1, f(1,2) = 2, f(2,1) = 2$ としてテーブルを埋めると以下のようになる。

f:id:imulan:20181019082521p:plain

よって、このアルゴリズムに従ってあとは操作列を出力すれば良いことになり、出力の行数も輪っか1つに対して10回が限度なので400000行ぐらいで、間に合う。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define fi first
#define se second

using pi = pair<int,int>;

const int INF = 123456;

struct State{
    int r,c;

    stack<int> st;
    // [mn,mx]の値を管理している
    int mn,mx;

    State(){
        mn = INF;
        mx = 0;
    }

    void PUSH(int v){
        st.push(v);
        mn = min(mn, v);
        mx = max(mx, v);
    }
};

int main(){
    vector<vector<int>> f(7,vector<int>(7));
    f[1][1] = 1;
    f[1][2] = f[2][1] = 2;
    for(int i=1; i<=6; ++i)for(int j=1; j<=6; ++j){
        if(f[i][j] != 0) continue;

        for(int r=1; r<=i; ++r)for(int c=1; c<=j; ++c){
            if(r==i && c==j) continue;
            f[i][j] += f[r][c];
        }
    }

    int n;
    scanf(" %d", &n);

    State ini;
    ini.r = ini.c = 6;
    rep(i,n){
        int d;
        scanf(" %d", &d);
        ini.PUSH(d);
    }

    vector<pi> mv(n+1);

    stack<State> st_st;
    st_st.push(ini);
    while(!st_st.empty()){
        State now = st_st.top();
        st_st.pop();

        int R = now.r, C = now.c;
        stack<int> s = now.st;
        int l = now.mn, r = now.mx;

        if(R==1 && C==1) continue;

        int posr = 7-R, posc = 7-C;

        if( (R==1&&C==2) || (R==2&&C==1) ){
            char dir = 'D';
            if(R==1) dir = 'R';

            int rem = r-l+1;

            if(rem == 2){ // 2個の場合は特殊な処理
                if(s.top() == l){ // 上が小さい方なので、2個一気に移動
                    printf("%d %d %c 2\n", posr, posc, dir);
                }
                else{ // 上が大きい方なので、1個ずつ移動
                    rep(i,2) printf("%d %d %c 1\n", posr, posc, dir);
                }
            }
            else{
                assert(rem == 1);
                printf("%d %d %c 1\n", posr, posc, dir);
            }
            continue;
        }

        // 各値の行き先を決定
        // ゴールに近い方から、大きい値を割り当てていく
        vector<vector<int>> cap(f);
        int nr = 1, nc = 1;
        for(int i=r; i>=l; --i){
            mv[i] = {nr,nc};
            --cap[nr][nc];

            if(cap[nr][nc] == 0){
                ++nc;
                if(nc==C+1){
                    nc = 1;
                    ++nr;
                }
            }
        }

        State nx[7][7];
        while(!s.empty()){
            int val = s.top();
            s.pop();

            // 実際に val を目的地へ移動させる
            int rr = mv[val].fi, cc = mv[val].se;
            nr = 7-rr;
            nc = 7-cc;

            for(int i=posr; i<nr; ++i) printf("%d %d D 1\n", i, posc);
            for(int i=posc; i<nc; ++i) printf("%d %d R 1\n", nr, i);

            nx[rr][cc].PUSH(val);
        }

        // 大きい値を先に処理したいので、stackには後でpushするようにする
        for(int i=R; i>=1; --i)for(int j=C; j>=1; --j){
            if(!nx[i][j].st.empty()){
                nx[i][j].r = i;
                nx[i][j].c = j;
                st_st.push(nx[i][j]);
            }
        }
    }

    return 0;
}

裏紙

ほぼ競プロ、たまに日記

CERC 2016 D - Dancing Disks

問題

問題概要

アイデア

実装(C++)