AtCoder Regular Contest #039 C問題 - 幼稚園児高橋君

Source

AtCoder Regular Contest #039
問題文

問題概要

無限に広い二次元のマス目がある．
最初マス $(0,0)$ にいて，各ステップでは，上下左右のいずれかの方向に，まだ訪れたことがないマスに辿り着くまで進む．
$K$ ステップ分だけ，どの方向に動くかが与えられるので，$K$ ステップ後にいる場所の座標を求める問題．

解法

訪れたことがある各マスについて，そのマスから上下左右のまだ訪れていないマスの座標を覚えておく．
それは，リストの構造みたいな感じで持てば，毎回の移動について $O(1)$ で処理することができる．
以下のコードでは，その情報は常に最新に保つわけではなく，Union Findの経路圧縮のような感じで計算した．
時間計算量はだいたい $O(K \log K)$ か $O(K)$ 程度．

C++によるスパゲッティなソースコード

#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)

#define ll long long
#define ull unsigned ll

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);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}

template<class T>
struct ullHash{
  ull *key; T *val; unsigned memory, size, mask;

  void clear(){memset(val,0,size*sizeof(T));}
  void clear(int sz){size=1;while(size<sz)size*=2;mask=size-1;clear();}
  void init(int mem, int sz){memory=mem;size=1;while(size<sz)size*=2;mask=size-1;if(memory<size)memory=size;key=(ull*)malloc(memory*sizeof(ull));val=(T*)malloc(memory*sizeof(T));if(size)clear();}
  int function(ull a){return (((a*123456789789ULL)>>32)*987654321321ULL)&mask;}
  T get(ull a){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;if(key[i]!=a) return 0;return val[i];}
  void set(ull a, T v){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;val[i]=v;}
  T increase(ull a, T v = 1){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;return val[i]+=v;}
};

int K;
char S[300000];

ullHash<int> ind;

int sz;
int x[300000], y[300000];
int up[300000], dw[300000], lef[300000], rig[300000];

int get_ind(ll X, ll Y){
  return ind.get((X+300000)*12345678LL + (Y+300000)) - 1;
}

void setxy(ll X, ll Y){
  x[sz] = X;
  y[sz] = Y;
  ind.set((X+300000)*12345678LL + (Y+300000), sz+1);
  up[sz] = Y+1;
  dw[sz] = Y-1;
  rig[sz] = X+1;
  lef[sz] = X-1;
  sz++;
}

void getxy(int &X, int &Y, char dir){
  int xx, yy, ind;

  ind = get_ind(X, Y);
  if(ind==-1) return;

  xx = X;
  yy = Y;
  if(dir=='U') yy = up[ind];
  if(dir=='D') yy = dw[ind];
  if(dir=='R') xx = rig[ind];
  if(dir=='L') xx = lef[ind];

  getxy(xx, yy, dir);
  if(dir=='U') up[ind] = yy;
  if(dir=='D') dw[ind] = yy;
  if(dir=='R') rig[ind] = xx;
  if(dir=='L') lef[ind] = xx;

  X = xx;
  Y = yy;
}


int main(){
  int i, X=0, Y=0;

  ind.init(300000,300000);

  reader(&K,S);
  setxy(X, Y);
  rep(i,K){
    getxy(X, Y, S[i]);
    setxy(X, Y);
  }

  writerLn(X,Y);

  return 0;
}

Current time: 2024年04月18日20時12分42秒
Last modified: 2015年07月01日07時00分59秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC039 ARC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：