M-SOLUTIONS プロコンオープン 2020 : F - Air Safety

やることは単純だけど面倒。
https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_f

問題

2次元座標上N個の点の初期位置(X[i],Y[i])と移動の向き(上下左右のいずれか)が与えられる。
各点が毎秒0.1の速さで移動するとき、最初に2点が衝突する時刻を答えよ。

解法

左右方向に移動する点同士が衝突する時刻を考える。
同じY座標上にある点を、X座標順にソートしよう。
隣接する2要素を見たとき、X座標の小さい方が右、大きい方が左に移動するなら、それらの衝突時刻は解の候補になる。
上下方向に移動する点同士も同じ。

あとは、上下に移動する点と左右に移動する点について考える。
例として、右に移動する点uと下に移動する点vのケースを考えよう。
これらが衝突する条件は、

• X[u]+Y[u]=X[v]+Y[v]である
• X[u]＜X[v]である

の両方を満たす場合である。
そこでX[u]+Y[u]が一致する頂点群をX座標順にソートし、上記のように隣接要素を比較すればよい。

右と下以外のケースも似た感じで対応できる。
X[u]+Y[u]ではなくX[u]-Y[u]が同じ点を集める場合もあるので注意。

int N;
int X[202020],Y[202020];
string U[202020];

vector<pair<int,int>> LR[402020],UD[402020],RU[402020],LD[402020],LU[402020],RD[402020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int ret=1<<30;
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i]>>U[i];
		
		if(U[i]=="L" || U[i]=="R") LR[Y[i]].push_back({X[i],i});
		if(U[i]=="U" || U[i]=="D") UD[X[i]].push_back({Y[i],i});
		if(U[i]=="L" || U[i]=="D") LD[X[i]+Y[i]].push_back({Y[i],i});
		if(U[i]=="R" || U[i]=="U") RU[X[i]+Y[i]].push_back({Y[i],i});
		if(U[i]=="L" || U[i]=="U") LU[Y[i]-X[i]+200000].push_back({X[i],i});
		if(U[i]=="R" || U[i]=="D") RD[Y[i]-X[i]+200000].push_back({X[i],i});
		
	}
	
	FOR(i,400001) {
		sort(ALL(LR[i]));
		sort(ALL(UD[i]));
		sort(ALL(LD[i]));
		sort(ALL(RU[i]));
		sort(ALL(LU[i]));
		sort(ALL(RD[i]));
		FOR(j,(int)LR[i].size()-1) if(U[LR[i][j].second]=="R"&&U[LR[i][j+1].second]=="L") ret=min(ret,(LR[i][j+1].first-LR[i][j].first)*5);
		FOR(j,(int)UD[i].size()-1) if(U[UD[i][j].second]=="U"&&U[UD[i][j+1].second]=="D") ret=min(ret,(UD[i][j+1].first-UD[i][j].first)*5);
		FOR(j,(int)LD[i].size()-1) if(U[LD[i][j].second]=="L"&&U[LD[i][j+1].second]=="D") ret=min(ret,(LD[i][j+1].first-LD[i][j].first)*10);
		FOR(j,(int)RU[i].size()-1) if(U[RU[i][j].second]=="U"&&U[RU[i][j+1].second]=="R") ret=min(ret,(RU[i][j+1].first-RU[i][j].first)*10);
		FOR(j,(int)LU[i].size()-1) if(U[LU[i][j].second]=="U"&&U[LU[i][j+1].second]=="L") ret=min(ret,(LU[i][j+1].first-LU[i][j].first)*10);
		FOR(j,(int)RD[i].size()-1) if(U[RD[i][j].second]=="R"&&U[RD[i][j+1].second]=="D") ret=min(ret,(RD[i][j+1].first-RD[i][j].first)*10);
		
	}
	
	
	
	if(ret==1<<30) {
		cout<<"SAFE"<<endl;
	}
	else {
		cout<<ret<<endl;
	}
}

まとめ

本番条件の大小順をミスって1WAしたので注意…。