問題

Dashboard - Round 2 2016 - Google Code Jam

問題概要

$R$ 行 $C$ 列のセルの中に，/または\の斜めの線を入れて迷路を作る．そして，そのセルの外周の四つ角以外の部分に左上から時計回りに順に番号を振る( $2 * (R+C)$ 個)．以下に，2*2行列の周りに番号が振られている例と迷路の一例を示す：

　１２
８＼／３
７／／４
　６５

今，この迷路を数字の位置を入り口として移動するともう一つの数字につながっている事がわかる．上の例では，(1,2),(3,6),(4,5),(7,8)の4つのペアがあると見なすことが出来る． $R$ と $C$ と $(R+C)$ 個の数字のペアが与えられるので，その全てのペアを結ぶような迷路が構成できる場合にはその構成を答え，ムリな場合にはIMPOSSIBLEと答えよ．

$1 \le R * C \le 100$

アイデア

公式の解説を見ながらまとめる．

まず，迷路の構成方法を全て試すのはムリ( $2^{R * C}$ 通り)．では，あるペアに対してその2つが繋がるようにその部分の迷路を構成してみるのはどうだろうか．最も単純な例を考えてみると，例えば上の図で1と8を繋ぎたいとなった場合に，左上のマスに/を入れるのが最もシンプルに実現できる方法である．もう少し複雑な構成方法があるかもしれないが，このシンプルな案を採用するデメリットが他のどの部分にも発生しないのでこうする方がよい．

次にシンプルなのは，辺上で隣り合う位置にあるときである．このようなときは三角形のように辺を結んでしまうのが一番簡単に実現できる．この場合も，このパスがあることによって他の部分に直接影響が出てしまうということはないし，この辺の張り方がベストであるといえる．

このようにあらゆるペアに対して最適なパスの作り方があるなら，それらを組み合わせていけばパーツが重ならなければ可能で重なったら失敗というように判定できそうだが，上の辺から下の辺へと縦断していくようなパスが必要になった場合，それがどのようにすれば最適なのかは他の状況との兼ね合いじゃないと決まるものではないし，このような考え方をしていくのは厳しそうである．ただ，そのような接続方法の上界と下界を考えることは出来る．ここでいう上界はそのつなぎ方をすれば最も多くのスペースを残すことが出来るつなぎ方であり，下界はその逆である．

以下では解があると仮定して議論を進めていくことにする．(もし本当に解があるならこれから考えていく方針はちゃんと条件を満たす迷路を構成できているはずである．逆にもし本当は解がないなら，実際に迷路をたどってみても条件を満たすようになっていないとチェックできるはずである．)

ここでグループというものを定義する．グループとは，1つ以上のペアが形成している道の集合全体を指す．例として，左側と右側を繋ぐようなペアがいる時，グループとはそのペアを繋ぐ道を指すとも言えるし，またその道を含んでいる集合とみなすこともできるということになる．

そして，どのようなグループにも最適な道集合があると考えることが出来る(ここで言う"最適"とは，お互いの道がかぶらないことを指す)．これをsufficiencyと呼ぶ．また，全てのペアを繋ぐ道集合が完成した時に，その道同士がどれもかぶっていないかどうかをnecessityと呼ぶ．

今，単純なペア(隣り合っている状況)のときにはどのような道が最適であるかはもうわかっている．そして，2つのグループがあってそれらを統合しようとするときに，最適なグループの統合方法はその2つのグループのそれぞれの最適な道集合の和集合になると考える．それがまたsufficiencyとneccesityを満たしていることが言えれば良い．そしてこれが正しいことを実際に確かめてみる．(いま，ここでは「解があると仮定」している．最終的に解が存在しないのならこの議論は不毛だが，今はとりあえずある状況を考えている．)

さて，それでは再び左の辺と右の辺にそれぞれの繋ぐべき頂点ペアがある場合を考えてみる．このペアに対して，最適なグループをもっていると仮定しよう．その時に今持っている最適なグループの道集合にこのペアの最適なグループを拡張して，統合出来るかどうかを試してみる．上で仮定された最適なグループにできるだけ近づけるような道集合を作ることを考えよう．そして，このようにして得られる道集合を最適なグループの道集合に統合するとそれもまた最適になっているということが言える．

これはどのような隣り合わないペアに対しても考えることができて，これを繰り返していくことで最適な道集合の全体を得ることが出来るというものである．

実装上はこのようになる：

まずはフィールドを線無しで初期化
2つのペアを，周辺をまわって移動した時の距離の小さい順にソートして，各ペアに対しては
- まずペアの番号を $A$ と $B$ として， $A$ から $B$ への移動が周辺を反時計回りに回ったほうが近くなるように並べておく．このようにに並べることによって今形成しようとしている $A$ から $B$ へのパスの左側はもう完成したと見なすことが出来る．(これは解があることを想定しているから成り立つことになる(はず)．)
- そして， $A$ からスタートして，できるだけ左寄りをキープしながら， $B$ への道を探す．もしそのセルに線がなければ左に進むようにしていく．もし線があるところに出くわしたらその方向にしたがって進んでいく．

このようにして辿り着く前に外に出てしまったりしたらその時点で失敗となり，解がないことになる．最後までできれば，解があるとみて答えれば良い．

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pi;
typedef pair<int, pi> ipi;

//coutierの位置と方向の関係をグリッド上に反映
ipi coutier_position(int num, int R, int C)
{
    if(num<=C) return ipi(0,pi(num-1,-1));
    num-=C;
    if(num<=R) return ipi(1,pi(C,num-1));
    num-=R;
    if(num<=C) return ipi(2,pi(C-num,R));
    num-=C;
    return ipi(3,pi(-1,R-num));
}

pi move(int x, int y, int direction)
{
    //下,左,上,右
    int dx[4]={0,-1,0,1}, dy[4]={1,0,-1,0};
    return pi(x+dx[direction], y+dy[direction]);
}

int main()
{
    int T;
    cin >>T;
    rep(t,T)
    {
        int r,c;
        cin >>r >>c;

        int NUM_PAIR = r+c;
        vector<pi> coutier(NUM_PAIR);
        vector<ipi> sorted_coutier(NUM_PAIR);
        rep(i,NUM_PAIR)
        {
            int x,y;
            scanf(" %d %d", &x, &y);
            //反時計まわりの方が早くなっている場合は入れ替える
            int dist_clockwise=0, dist_counterclockwise=0;
            if(x<y)
            {
                dist_clockwise = y-x;
                dist_counterclockwise = 2*(r+c) - dist_clockwise;
            }
            else
            {
                dist_counterclockwise = x-y;
                dist_clockwise = 2*(r+c) - dist_counterclockwise;
            }
            if(dist_clockwise < dist_counterclockwise) swap(x,y);
            coutier[i]=pi(x,y);
            sorted_coutier[i] = ipi(min(dist_clockwise, dist_counterclockwise), pi(x,y));
        }
        sort(all(sorted_coutier));
        //ソートを反映
        rep(i,NUM_PAIR) coutier[i] = sorted_coutier[i].se;

        //順番に処理
        bool valid = true;
        vector<string> ans(r, string(c,' '));
        rep(i,NUM_PAIR)
        {
            int start=coutier[i].fi, end=coutier[i].se;
            // printf("%d: %d to %d\n", i,start,end);

            ipi s=coutier_position(start, r, c);
            int dir=s.fi, x=s.se.fi, y=s.se.se;
            pi nxt=move(x,y,dir);
            x=nxt.fi; y=nxt.se;
            //グリッドから出るまで
            while(0<=y&&y<r && 0<=x&&x<c)
            {
                //まだその位置の壁が決まっていない時はできるだけ寄るように
                if(ans[y][x]==' ')
                {
                    int wall=dir&1;
                    string w="/\\";
                    ans[y][x]=w[wall];
                }
                //方向転換
                int mirror=3;
                if(ans[y][x]=='/') mirror=1;
                dir^=mirror;
                //移動
                nxt=move(x,y,dir);
                x=nxt.fi; y=nxt.se;
            }

            if(pi(x,y) != coutier_position(end,r,c).se)
            {
                valid=false;
                break;
            }
        }

        //output
        printf("Case #%d:\n", t+1);
        if(valid)
        {
            //空白は適当に埋めて良い
            rep(i,r)rep(j,c) if(ans[i][j]==' ') ans[i][j]='/';
            rep(i,r) cout << ans[i] << endl;
        }
        else printf("IMPOSSIBLE\n");
    }
    return 0;
}

今年のGCJ Round2が終わってからできなかった問題の復習を書き始めていたんだけど，これ解説みてもいまいちピンとこなかったのでとりあえずこの時期まで放置されていた．それでもまだ完璧に理解しきれていないので理解が深まったらまたこれを更新するかも．

裏紙

ほぼ競プロ、たまに日記

GCJ 2016 Round2 C - The Gardener of Seville

問題

問題概要

アイデア

実装(C++)