HackerRank Weekly Challenges - Week 2 3問目 - Huarongdao

Source

HackerRank Weekly Challenges - Week 2 3問目
problem statement(コンテストページ)
problem statement

問題概要

$N$ 行 $M$ 列の盤面が与えられる.
各セルは $0$ か $1$ で,$0$ は動かせないブロックが,$1$ は動かせるブロックが置かれていることを表している.
また,正整数 $K$ が与えられ,これは全てにクエリに対して一定の整数である.
そのような盤面に$Q$ 個のクエリが与えられる.
各クエリ $(E_x, E_y, S_x, S_y, T_x, T_y)$ に対して,ゲームをクリアするための最短秒数を求める,あるいは,クリアできないことを指摘する問題.
ゲームのルールは以下の通り.
$(E_x, E_y)$ のセルのブロックを取り外す.
$(S_x, S_y)$ のセルのブロックを特殊なブロックに変更する.
各動かせるブロックと特殊なブロックは,移動先が空いているのであれば,$1$ 秒かけて上下左右に $1$ マス移動できる.
特殊なブロックでない,動かせるブロックは,$K$ 秒かけることで,取り外して,空の場所であった場所に移動できる.(どんなに遠くても移動可能)
特殊なブロックを $(T_x, T_y)$ に移動させたらゲームクリア.
$(E_x, E_y), (S_x, S_y), (T_x, T_y)$ はそれぞれ $1$ のセル(動かせるブロックのセル)を指し示している.

解法

特殊なブロックを動かすためには,その動かしたい方向,上下左右,に空マスでなくてはいけない.
そこで,特殊なブロックの位置と,上下左右のどこに空マスがあるかを状態として,ダイクストラする.
特殊なブロックの位置を動かさずに,特殊なブロックの上下左右にある空マスの位置を,特殊なブロックの上下左右に移動させるコストは,クエリを処理する前に全部計算しておく.
この時,空マスの位置が上下左右に動けるとしてBFSすれば良いが,(目的地が動かせるブロックであれば)$K$ でワープして動かすことができるので,$K-1$ マス以下の距離までしか見なくて良い.
同様に,クエリごとに,最初に空マスがある位置から,特殊なブロックの上下左右に移動させるのに必要なコストを調べるときも,距離 $K-1$ 以下のマスだけBFSして調べれば良い.
ダイクストラで使う枝のコストは,高々 $K$ か,特殊なブロックの移動も同時に考えても $K+1$ なので,スタックを $K+2$ 個使って行うと時間計算量から $\log$ が消える.
時間計算量は2分ヒープを使ってダイクストラで $O(NMK^2 + QNM \log NM)$ で,スタックを用いると $O(NMK^2 + QNM)$ 程度.

コンテスト本番では最悪ケースがないため十分高速に通るが,その後,最悪ケースが追加されたらしく,これでは通らなくなった.

C++によるスパゲッティなソースコード(2分ヒープ)

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

template <class T>
struct DijkstraHeap {
  int *hp, *place, size; char *visited; T *val;

  void* malloc(int N, void *workMemory){hp=(int*)workMemory;place=(int*)(hp+N);visited=(char*)(place+N);val=(T*)(visited+N);workMemory=(void*)(val+N);return workMemory;}
  void init(int N){int i;size=0;rep(i,N)place[i]=-1,visited[i]=0;}
  void up(int n){int m;while(n){m=(n-1)/2;if(val[hp[m]]<=val[hp[n]])break;swap(hp[m],hp[n]);swap(place[hp[m]],place[hp[n]]);n=m;}}
  void down(int n){int m;for(;;){m=2*n+1;if(m>=size)break;if(m+1<size&&val[hp[m]]>val[hp[m+1]])m++;if(val[hp[m]]>=val[hp[n]]) break;swap(hp[m],hp[n]);swap(place[hp[m]],place[hp[n]]);n=m;}}
  void change(int n, T v){if(visited[n]||(place[n]>=0&&val[n]<=v))return;val[n]=v;if(place[n]==-1)place[n]=size,hp[size++]=n,up(place[n]);else up(place[n]);}
  int pop(void){int res=hp[0];place[res]=-1;hp[0]=hp[--size];place[hp[0]]=0;down(0);visited[res]=1;return res;}
};

#define INF 1000000000
#define isValid(i,j) (mp[i][j])

int X, Y, Q, K;
int EX, EY, SX, SY, TX, TY;
int mp[210][210];

int cost[210][210][4][4];

int visited[210][210], viscnt = 0, dist[210][210];
int q[50000], q_st, q_size;

int mem[10000000];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void bfs(int sx, int sy, int lim){
  int l, sd, nx, ny;
  
  viscnt++;
  dist[sx][sy] = 0;
  visited[sx][sy] = viscnt;
  q_st = q_size = 0;
  q[q_st+q_size++] = (sx<<10) + sy;
  while(q_size){
    l = q[q_st++]; q_size--;
    sx = (l>>10); sy = (l&((1<<10)-1));
    if(dist[sx][sy]==lim-1) break;
    rep(sd,4){
      nx = sx + dx[sd];
      ny = sy + dy[sd];
      if((!isValid(nx,ny))||visited[nx][ny]==viscnt) continue;
      visited[nx][ny] = viscnt;
      dist[nx][ny] = dist[sx][sy] + 1;
      q[q_st+q_size++] = (nx<<10) + ny;
    }
  }
}

int main(){
  int i, j, k, l, ind;
  int sx, sy, sd, nx, ny, nd, nc;
  DijkstraHeap<int> hp;
  int res;

  hp.malloc(210*210*4, mem);

  reader(&X, &Y);
  reader(&K, &Q);
  rep(i,X) rep(j,Y) reader(mp[i+1]+j+1);
  X += 2;
  Y += 2;
  rep(i,X) mp[i][0] = mp[i][Y-1] = 0;
  rep(j,Y) mp[0][j] = mp[X-1][j] = 0;

  rep(i,X) rep(j,Y) rep(k,4){
    sx = i + dx[k];
    sy = j + dy[k];
    if(!isValid(i,j) || !isValid(sx,sy)){
      rep(l,4) cost[i][j][k][l] = INF;
      continue;
    }

    mp[i][j]=0;
    bfs(sx, sy, K);
    mp[i][j]=1;
    rep(l,4){
      sx = i + dx[l];
      sy = j + dy[l];
      if(!isValid(sx,sy))              cost[i][j][k][l] = INF;
      else if(visited[sx][sy]!=viscnt) cost[i][j][k][l] = K;
      else                             cost[i][j][k][l] = dist[sx][sy];
    }
  }

  while(Q--){
    reader(&EX, &EY);
    reader(&SX, &SY);
    reader(&TX, &TY);
    res = -1;

    if(SX==TX && SY==TY){
      writer(0, '\n');
      continue;
    }

    hp.init(X*Y*4);

    mp[SX][SY] = 0;
    bfs(EX, EY, K);
    mp[SX][SY] = 1;
    rep(k,4){
      sx = SX + dx[k];
      sy = SY + dy[k];
      if(!isValid(sx,sy)) continue;
      if(visited[sx][sy]==viscnt) l = dist[sx][sy]; else l = K;
      hp.change((SX*Y+SY)*4+k, l);
    }

    while(hp.size){
      ind = l = hp.pop();
      sd = l%4; l/=4;
      sx = l/Y; sy = l%Y;

      if(sx==TX && sy==TY){ res = hp.val[ind]; break; }
      rep(nd, 4) if(cost[sx][sy][sd][nd]!=INF){
        nc = hp.val[ind] + cost[sx][sy][sd][nd] + 1;
        nx = sx + dx[nd];
        ny = sy + dy[nd];
        hp.change((nx*Y+ny)*4+(nd^2), nc);
      }
    }

    writer(res, '\n');
  }

  return 0;
}

C++によるスパゲッティなソースコード($K+2$個のスタック)

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

struct DijkstraManyStack{
  unsigned lim, last, mask; int *val; stack<int> *st;
  void malloc(int N, int L){val=new int[N];st=new stack<int>[2*L];}
  void init(int N, int L){int i;lim=1;while(lim<L)lim*=2;mask=lim-1;last=0;memset(val,-1,N*sizeof(int));rep(i,lim)while(st[i].size())st[i].pop();}
  void change(int n, int v){if(val[n]!=-1&&val[n]<=v)return;val[n]=v;st[v&mask].push(n);}
  int pop(void){int i,k;rep(i,lim){while(st[last&mask].size()){k=st[last&mask].top();st[last&mask].pop();if(val[k]>last)continue;return k;}last++;}return -1;}
};

#define INF 1000000000
#define isValid(i,j) (mp[i][j])

int X, Y, Q, K;
int EX, EY, SX, SY, TX, TY;
int mp[210][210];

int cost[210][210][4][4];

int visited[210][210], viscnt = 0, dist[210][210];
int q[50000], q_st, q_size;

int dd[210][210][4];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void bfs(int sx, int sy, int lim){
  int l, sd, nx, ny;
  
  viscnt++;
  dist[sx][sy] = 0;
  visited[sx][sy] = viscnt;
  q_st = q_size = 0;
  q[q_st+q_size++] = (sx<<10) + sy;
  while(q_size){
    l = q[q_st++]; q_size--;
    sx = (l>>10); sy = (l&((1<<10)-1));
    if(dist[sx][sy]==lim-1) break;
    rep(sd,4){
      nx = sx + dx[sd];
      ny = sy + dy[sd];
      if((!isValid(nx,ny))||visited[nx][ny]==viscnt) continue;
      visited[nx][ny] = viscnt;
      dist[nx][ny] = dist[sx][sy] + 1;
      q[q_st+q_size++] = (nx<<10) + ny;
    }
  }
}

int main(){
  int i, j, k, l, ind;
  int sx, sy, sd, nx, ny, nd, nc, c, las;
  int res;
  DijkstraManyStack hp;

  reader(&X, &Y);
  reader(&K, &Q);
  rep(i,X) rep(j,Y) reader(mp[i+1]+j+1);
  X += 2;
  Y += 2;
  rep(i,X) mp[i][0] = mp[i][Y-1] = 0;
  rep(j,Y) mp[0][j] = mp[X-1][j] = 0;

  rep(i,X) rep(j,Y) rep(k,4){
    sx = i + dx[k];
    sy = j + dy[k];
    if(!isValid(i,j) || !isValid(sx,sy)){
      rep(l,4) cost[i][j][k][l] = INF;
      continue;
    }

    mp[i][j]=0;
    bfs(sx, sy, K);
    mp[i][j]=1;
    rep(l,4){
      sx = i + dx[l];
      sy = j + dy[l];
      if(!isValid(sx,sy))              cost[i][j][k][l] = INF;
      else if(visited[sx][sy]!=viscnt) cost[i][j][k][l] = K;
      else                             cost[i][j][k][l] = dist[sx][sy];
    }
  }

  hp.malloc(210*210*4, 32);

  while(Q--){
    reader(&EX, &EY);
    reader(&SX, &SY);
    reader(&TX, &TY);
    res = -1;

    if(SX==TX && SY==TY){
      writer(0, '\n');
      continue;
    }

    hp.init(X*Y*4, 64);

    rep(i,X) rep(j,Y) rep(k,4) dd[i][j][k] = INF;

    mp[SX][SY] = 0;
    bfs(EX, EY, K);
    mp[SX][SY] = 1;
    rep(k,4){
      sx = SX + dx[k];
      sy = SY + dy[k];
      if(!isValid(sx,sy)) continue;
      if(visited[sx][sy]==viscnt) l = dist[sx][sy]; else l = K;
      hp.change((SX*Y+SY)*4+k, l);
    }

    las = 0;
    for(;;){
      ind = l = hp.pop();
      if(ind==-1) break;
      sd = l%4; l/=4;
      sx = l/Y; sy = l%Y;

      if(sx==TX && sy==TY){ res = hp.val[ind]; break; }
      rep(nd, 4) if(cost[sx][sy][sd][nd]!=INF){
        nc = hp.val[ind] + cost[sx][sy][sd][nd] + 1;
        nx = sx + dx[nd];
        ny = sy + dy[nd];
        hp.change((nx*Y+ny)*4+(nd^2), nc);
      }
    }
    
    writer(res, '\n');
  }

  return 0;
}

Current time: 2017年07月21日13時34分38秒
Last modified: 2014年09月22日23時36分07秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_w2
トップページに戻る

Logged in as: unknown user (not login)

ログイン: