AtCoder ARC #039 : C - 幼稚園児高橋君

データ構造をガリガリ頑張る問題。
http://arc039.contest.atcoder.jp/tasks/arc039_c

問題

初期状態でプレイヤーは二次元座標の原点にいる。

ここでK文字のコマンド列が与えられる。
各コマンドは上下左右に対応しており、プレイヤーは座標上その向きに隣接する格子点を順々に進む。
初めて到達した格子点に来たら、そのコマンドは終了する。

K文字分のコマンド列を処理した後、プレイヤーのいる座標を求めよ。

解法

以下のデータ構造を駆使して処理する。

• X座標ごとに未到達のY座標の区間の集合を管理
• Y座標ごとに未到達のX座標の区間の集合を管理

左に進む場合、後者のデータをlower_bound等で探索して現在位置の左側直近の未到達区間を求める。
そしてそこに移動して、未到達区間の情報を更新する。
同様に上下右も処理する。

1コマンドごとに、上記2つの両方のデータ構造を更新していけば良い。

int K;
string S;

set<pair<int,int> > XS[404000],YS[404000];

int moveto(set<pair<int,int> >& SS, int v,int dir) {
	auto it=SS.lower_bound(make_pair(v,v));
	if(dir) it--;
	auto r=*it;
	SS.erase(it);
	
	if(dir) v=r.second--;
	else v=r.first++;
	
	if(r.first<=r.second) SS.insert(r);
	return v;
}

void insertto(set<pair<int,int> >& SS, int v) {
	auto it=SS.lower_bound(make_pair(v,v));
	if(it==SS.end() || it->first>v) it--;
	
	auto r=*it,r2=*it;
	SS.erase(r);
	
	r.second=v-1;
	r2.first=v+1;
	
	if(r.first<=r.second) SS.insert(r);
	if(r2.first<=r2.second) SS.insert(r2);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>S;
	FOR(i,404000) XS[i].insert(make_pair(0,404000));
	FOR(i,404000) YS[i].insert(make_pair(0,404000));
	
	x=202000,y=202000;
	insertto(XS[y],x);
	insertto(YS[x],y);
	
	FORR(c,S) {
		if(c=='U' || c=='D') {
			y=moveto(YS[x],y,c=='D');
			insertto(XS[y],x);
		}
		if(c=='L' || c=='R') {
			x=moveto(XS[y],x,c=='L');
			insertto(YS[x],y);
		}
	}
	_P("%d %d\n",x-202000,y-202000);
}

まとめ

結構実装が面倒だ。
もっと簡潔に書けないかな。